Chris M. Thomasson wrote:
> I was thinking of an idea of expanding a current limitation in some of
> my allocators which sup****t the use of header-less blocks. The way I
> currently do it is to simply align chunks on a fairly large boundary,
> say 16 pages. These chunks contain a header at the head. Layout is
simple:
>
> [H][CHUNK]
>
> A 16-page chunk would be aligned on a 16-page chunk boundary. If a
> header-less block needs to access its header, it simple rounds its
> address up to a chunk boundary, and subtracts the size of the chunk plus
> the size of the header. This has a limitation that the largest memory
> allocation can't be larger than the size of a chunk. To overcome this, I
> was thinking about generating a unique GUID per-computer, and using that
> as a header identifier. The header would store the GUID right after it.
> So, the layout for a multi-chunk allocation would look like:
>
>
> [H][GUID][CHUNK1][CHUNK2]
>
>
> Now, when a header-less block needs to find its chunk header it simply,
> rounds its address up to a chunk boundary; subtracts the size of the
> chunk plus the size of the GUID; compares the existing memory contents
> with the GUID; if it does not find a match, it subtracts the size of the
> a chunk minus the size of the GUID and repeats the comparison. This
> process is repeated until a match is hit. After that, it subtracts the
> size of the header, and bingo, it has a pointer to its chunk header.
>
> The process is simple but is has a caveat! If for some reason, the
> memory contents of a chunk that is not the true header just happens to
> contain data which matches the GUID, well, BOOOOOM!!!!!!! Oh ****%!!! The
> program will be royally screwed... OUCH!
>
>
> First of all, what do you think of the scheme?
A couple questions arise right away. First, what information
does this header provide; why do you need it; what's it for? Second,
how does a chunk discover its own size? Are all chunks the same
fixed size, or is the size stored somewhere in the chunk -- and if
you're already storing metadata in the chunk, why not store the
rest of the header there, too?
An observation: The GUID doesn't seem to add much value. Any
unlikely signature would do just as well -- that is to say, just as
poorly.
A counter-question: Why must headers be adjacent to chunks? Would
it help if they lived in their own dedicated data structure? I've used
skip-lists in a separate area for this purpose as part of a malloc()
intended for debugging; keeping the metadata apart from the allocated
data helps limit the damage from common programming errors.
> Also, are there better ways to sup****t 100% header-less blocks in a
> memory allocator? IMVHO, header-less blocks are a MAJOR plus when
> designing highly efficient memory allocation implementations. Think
> about it... A 4-byte allocation actually means 4-bytes are allocated
> internally. No 4-bytes plus internal block header information! That's
> crap and totally wastes memory on a per-allocation basis; which can
> quickly add up indeed.
Well, you need *some* way to store the size information, and maybe
other information as well. I suppose you could use the block address
to encode size: A block address of binary ...xxx100 would indicate a
size of four bytes, ...xx1000 would indicate eight bytes, and so on.
Fragmentation would be horrific, though.
> There is a way to minimize the GUID scheme, but it requires two sections
> of virtual memory which can be wasteful. It involves block sizes <=
> chunk size to be allocated from a separate memory pool than block sizes
> that are > chunk size. The former can use the normal scheme of simple
> rounding up and subtracting to get chunk header... However, the latter
> would need to use the GUID search algorithm.
You haven't described your allocator's purposes and constraints
fully enough for me to follow this paragraph.
--
Eric.Sosman@[EMAIL PROTECTED]
|
