2 * Copyright 2000, International Business Machines Corporation and others.
5 * This software has been released under the terms of the IBM Public
6 * License. For details, see the LICENSE file in the top-level source
7 * directory or online at http://www.openafs.org/dl/license10.html
11 #include "../afs/afs_atomlist.h"
13 #include "afs_atomlist.h"
17 * The afs_atomlist abstract data type is for efficiently allocating
18 * space for small structures.
20 * The atoms in an afs_atomlist are allocated in blocks. The blocks
21 * are chained together so that they can be freed when the afs_atomlist
22 * is destroyed. When a new block is allocated, its atoms are chained
23 * together and added to the free list of atoms.
25 * If the requested atom size is smaller than the size of a pointer,
26 * afs_atomlist_create() silently increases the atom size. If
27 * the atom size would result in incorrectly aligned pointers,
28 * afs_atomlist_create() silently increases the atom size as necessary.
30 * A block of atoms is organized as follows.
32 * ---------------------------------------------------------------
33 * | atom | atom | atom | ... | atom | nextblock | wasted space* |
34 * ---------------------------------------------------------------
35 * \____ atoms_per_block atoms ______/
37 * (*) A block may or may not contain wasted space at the end. The
38 * amount of wasted space depends on the size of a block, the size of an
39 * atom, and the size of the pointer to the next block. For instance,
40 * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4
41 * bytes, there is no wasted space in a block.
43 * The pointer to the next block is stored AFTER all the atoms in the
46 * If we put the pointer to the next block before the atoms,
47 * followed immediately by the atoms, we would be assuming that the
48 * atoms could be aligned on a pointer boundary.
50 * If we tried to solve the alignment problem by allocating an entire
51 * atom for the pointer to the next block, we might waste space
52 * gratuitously. Say a block is 4096 bytes, an atom is 24 bytes, and a
53 * pointer is 8 bytes. In this case a block can hold 170 atoms, with 16
54 * bytes left over. This isn't enough space for another atom, but it is
55 * enough space for the pointer to the next block. There is no need to
56 * use one of the atoms to store the pointer to the next block.
58 * So, we store the pointer to the next block after the end of the atoms
59 * in the block. In the worst case, the block size is an exact multiple
60 * of the atom size, and we waste an entire atom to store the pointer to
61 * the next block. But we hope it is more typical that there is enough
62 * extra space after the atoms to store the pointer to the next block.
64 * A more sophisticated scheme would keep the pointers to the atom
65 * blocks in a separate list of blocks. It would eliminate the
66 * fragmentation of the atom blocks in the case where the block size
67 * is a multiple of the atom size. However, it is more complicated to
68 * understand and to implement, so I chose not to do it at this time.
69 * If fragmentation turns out to be a serious enough issue, we can
70 * change the afs_atomlist implementation without affecting its users.
76 size_t atoms_per_block;
77 void *(*allocate)(size_t n);
78 void (*deallocate)(void *p, size_t n);
79 void *atom_head; /* pointer to head of atom free list */
80 void *block_head; /* pointer to block list */
87 , void *(*allocate)(size_t n)
88 , void (*deallocate)(void *p, size_t n)
92 size_t atoms_per_block;
96 * Atoms must be at least as big as a pointer in order for
97 * our implementation of the atom free list to work.
99 if (atom_size < sizeof(void *)) {
100 atom_size = sizeof(void *);
104 * Atoms must be a multiple of the size of a pointer
105 * so that the pointers in the atom free list will be
108 if (atom_size % sizeof(void *) != (size_t)0) {
109 size_t pad = sizeof(void *) - (atom_size % sizeof(void *));
114 * Blocks are the unit of memory allocation.
116 * 1) Atoms are allocated out of blocks.
118 * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *)
119 * boundary, are used to chain together the blocks so that they can
120 * be freed later. This reduces the space in each block for atoms.
121 * It is intended that atoms should be small relative to the size of
122 * a block, so this should not be a problem.
124 * At a minimum, a block must be big enough for one atom and
125 * a pointer to the next block.
127 if (block_size < atom_size + sizeof(void *))
130 atoms_per_block = block_size / atom_size;
131 extra_space = block_size - (atoms_per_block * atom_size);
132 if (extra_space < sizeof(void *)) {
133 if (atoms_per_block < (size_t)2) {
134 return 0; /* INTERNAL ERROR! */
139 al = allocate(sizeof *al);
143 al->atom_size = atom_size;
144 al->block_size = block_size;
145 al->allocate = allocate;
146 al->deallocate = deallocate;
149 al->atoms_per_block = atoms_per_block;
162 for(cur = al->block_head; cur; cur = next) {
163 next = *(void **)((char *)cur + al->atoms_per_block * al->atom_size);
164 al->deallocate(cur, al->block_size);
166 al->deallocate(al, sizeof *al);
176 /* allocate a new block if necessary */
177 if (!al->atom_head) {
182 block = al->allocate(al->block_size);
187 /* add this block to the chain of allocated blocks */
188 *(void **)((char *)block + al->atoms_per_block * al->atom_size) =
190 al->block_head = block;
192 /* add this block's atoms to the atom free list */
194 for (i = 0; i+1 < al->atoms_per_block; i++) {
195 *(void **)p = (char *)p + al->atom_size;
196 p = (char *)p + al->atom_size;
199 al->atom_head = block;
202 if (!al->atom_head) {
203 return 0; /* INTERNAL ERROR */
206 data = al->atom_head;
207 al->atom_head = *(void **)data;
218 *(void **)data = al->atom_head;
219 al->atom_head = data;