10.  Appendix A - Implementation Details

/*
 * Constants for setting the parameters of the kernel memory allocator.
 *
 * 2 ** MINBUCKET is the smallest unit of memory that will be
 * allocated. It must be at least large enough to hold a pointer.
 *
 * Units of memory less or equal to MAXALLOCSAVE will permanently
 * allocate physical memory; requests for these size pieces of memory
 * are quite fast. Allocations greater than MAXALLOCSAVE must
 * always allocate and free physical memory; requests for these size
 * allocations should be done infrequently as they will be slow.
 * Constraints: CLBYTES <= MAXALLOCSAVE <= 2 ** (MINBUCKET + 14)
 * and MAXALLOCSIZE must be a power of two.
 */
#define MINBUCKET4/* 4 => min allocation of 16 bytes */
                                                     MAXALLOCSAVE#define MAXALLOCSAVE(2 * CLBYTES)

/*
 * Maximum amount of kernel dynamic memory.
 * Constraints: must be a multiple of the pagesize.
 */
                                                          MAXKMEM#define MAXKMEM(1024 * PAGESIZE)

/*
 * Arena for all kernel dynamic memory allocation.
 * This arena is known to start on a page boundary.
 */
extern char kmembase[MAXKMEM];

/*
 * Array of descriptors that describe the contents of each page
 */
struct kmemsizes {
shortks-indx;/* bucket index, size of small allocations */
u-shortks-pagecnt;/* for large allocations, pages allocated */
} kmemsizes[MAXKMEM / PAGESIZE];

/*
 * Set of buckets for each size of memory block that is retained
 */
struct kmembuckets {
caddr-t kb-next;/* list of free blocks */
} bucket[MINBUCKET + 16];
/*
 * Macro to convert a size to a bucket index. If the size is constant,
 * this macro reduces to a compile time constant.
 */
                                                     MINALLOCSIZE#define MINALLOCSIZE(1 << MINBUCKET)
                                                       BUCKETINDX#define BUCKETINDX(size) \
(size) <= (MINALLOCSIZE * 128) \
? (size) <= (MINALLOCSIZE * 8) \
? (size) <= (MINALLOCSIZE * 2) \
? (size) <= (MINALLOCSIZE * 1) \
? (MINBUCKET + 0) \
: (MINBUCKET + 1) \
: (size) <= (MINALLOCSIZE * 4) \
? (MINBUCKET + 2) \
: (MINBUCKET + 3) \
: (size) <= (MINALLOCSIZE* 32) \
? (size) <= (MINALLOCSIZE * 16) \
? (MINBUCKET + 4) \
: (MINBUCKET + 5) \
: (size) <= (MINALLOCSIZE * 64) \
? (MINBUCKET + 6) \
: (MINBUCKET + 7) \
: (size) <= (MINALLOCSIZE * 2048) \
/* etc ... */

/*
 * Macro versions for the usual cases of malloc/free
 */
                                                           MALLOC#define MALLOC(space, cast, size, flags) { \
register struct kmembuckets *kbp = &bucket[BUCKETINDX(size)]; \
long s = splimp(); \
if (kbp->kb-next == NULL) { \
(space) = (cast)malloc(size, flags); \
} else { \
(space) = (cast)kbp->kb-next; \
kbp->kb-next = *(caddr-t *)(space); \
} \
splx(s); \
}

                                                             FREE#define FREE(addr) { \
register struct kmembuckets *kbp; \
register struct kmemsizes *ksp = \
&kmemsizes[((addr) - kmembase) / PAGESIZE]; \
long s = splimp(); \
if (1 << ksp->ks-indx > MAXALLOCSAVE) { \
free(addr); \
} else { \
kbp = &bucket[ksp->ks-indx]; \
*(caddr-t *)(addr) = kbp->kb-next; \
kbp->kb-next = (caddr-t)(addr); \
} \
splx(s); \
}