All pastes #358034 Raw Edit

Block design

public text v1 · immutable
·published 2007-02-16 01:20 UTC
rendered paste body
/*
 * The following is the structure of a FREE block:
 *   +--------------------+ 
 *   | sz w/ lsbit = 0    | 1 word
 *   | list next ptr      | 1 word
 *   +--------------------+
 *   | free space         | min 0 bytes
 *   |                    | max n dwords (so always 0 mod 8 bytes)
 *            ...
 *   |                    |
 *   +--------------------+
 *   | list prev ptr      | 1 word
 *   | sz w/ LSbit = 0    | 1 word
 *   +--------------------+
 *
 * The following is the structure of an ALLOCATED block:
 *   +--------------------+ 
 *   | sz w/ lsbit = 0    | 1 word
 *   +--------------------+
 *   | payload            | min 1 dword
 *   |                    | max n dwords (so always 0 mod 8 bytes)
 *   |                    |
 *            ...
 *   |                    |
 *   |                    |
 *   +--------------------+
 *   | sz w/ LSbit = 0    | 1 word
 *   +--------------------+
 *
 * Notice how the header and footer sizes for an allocated block have shrunk by
 * a word each. This is because an allocated block does not need to keep track
 * of succ/next pointers, since it is not a member of any free list. So, the
 * space used by these pointers in a free block becomes payload in an allocated
 * block. (Since 2 words = 8 bytes, alignment is preserved.) However, this al-
 * lows free blocks to exist which have 0 bytes of "free space". The size kept
 * in the header and footer gives all potential payload, including the free
 * space and the two pointers. Thus, although there may be no additional free
 * space in the block, the minimum size value is 8 bytes. The size does NOT in-
 * clude the space used to maintain its own value; if you wish to do pointer
 * arithmetic, make sure to account for HDR_SZ and FTR_SZ.
 */