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
10 #include <afsconfig.h>
11 #include <afs/param.h>
17 #include "afs_atomlist.h"
19 #include "afs_atomlist.h"
23 * The afs_atomlist abstract data type is for efficiently allocating
24 * space for small structures.
26 * The atoms in an afs_atomlist are allocated in blocks. The blocks
27 * are chained together so that they can be freed when the afs_atomlist
28 * is destroyed. When a new block is allocated, its atoms are chained
29 * together and added to the free list of atoms.
31 * If the requested atom size is smaller than the size of a pointer,
32 * afs_atomlist_create() silently increases the atom size. If
33 * the atom size would result in incorrectly aligned pointers,
34 * afs_atomlist_create() silently increases the atom size as necessary.
36 * A block of atoms is organized as follows.
38 * ---------------------------------------------------------------
39 * | atom | atom | atom | ... | atom | nextblock | wasted space* |
40 * ---------------------------------------------------------------
41 * \____ atoms_per_block atoms ______/
43 * (*) A block may or may not contain wasted space at the end. The
44 * amount of wasted space depends on the size of a block, the size of an
45 * atom, and the size of the pointer to the next block. For instance,
46 * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4
47 * bytes, there is no wasted space in a block.
49 * The pointer to the next block is stored AFTER all the atoms in the
52 * If we put the pointer to the next block before the atoms,
53 * followed immediately by the atoms, we would be assuming that the
54 * atoms could be aligned on a pointer boundary.
56 * If we tried to solve the alignment problem by allocating an entire
57 * atom for the pointer to the next block, we might waste space
58 * gratuitously. Say a block is 4096 bytes, an atom is 24 bytes, and a
59 * pointer is 8 bytes. In this case a block can hold 170 atoms, with 16
60 * bytes left over. This isn't enough space for another atom, but it is
61 * enough space for the pointer to the next block. There is no need to
62 * use one of the atoms to store the pointer to the next block.
64 * So, we store the pointer to the next block after the end of the atoms
65 * in the block. In the worst case, the block size is an exact multiple
66 * of the atom size, and we waste an entire atom to store the pointer to
67 * the next block. But we hope it is more typical that there is enough
68 * extra space after the atoms to store the pointer to the next block.
70 * A more sophisticated scheme would keep the pointers to the atom
71 * blocks in a separate list of blocks. It would eliminate the
72 * fragmentation of the atom blocks in the case where the block size
73 * is a multiple of the atom size. However, it is more complicated to
74 * understand and to implement, so I chose not to do it at this time.
75 * If fragmentation turns out to be a serious enough issue, we can
76 * change the afs_atomlist implementation without affecting its users.
82 size_t atoms_per_block;
83 void *(*allocate) (size_t n);
84 void (*deallocate) (void *p, size_t n);
85 void *atom_head; /* pointer to head of atom free list */
86 void *block_head; /* pointer to block list */
90 afs_atomlist_create(size_t atom_size, size_t block_size,
91 void *(*allocate) (size_t n)
92 , void (*deallocate) (void *p, size_t n)
96 size_t atoms_per_block;
100 * Atoms must be at least as big as a pointer in order for
101 * our implementation of the atom free list to work.
103 if (atom_size < sizeof(void *)) {
104 atom_size = sizeof(void *);
108 * Atoms must be a multiple of the size of a pointer
109 * so that the pointers in the atom free list will be
112 if (atom_size % sizeof(void *) != (size_t) 0) {
113 size_t pad = sizeof(void *) - (atom_size % sizeof(void *));
118 * Blocks are the unit of memory allocation.
120 * 1) Atoms are allocated out of blocks.
122 * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *)
123 * boundary, are used to chain together the blocks so that they can
124 * be freed later. This reduces the space in each block for atoms.
125 * It is intended that atoms should be small relative to the size of
126 * a block, so this should not be a problem.
128 * At a minimum, a block must be big enough for one atom and
129 * a pointer to the next block.
131 if (block_size < atom_size + sizeof(void *))
134 atoms_per_block = block_size / atom_size;
135 extra_space = block_size - (atoms_per_block * atom_size);
136 if (extra_space < sizeof(void *)) {
137 if (atoms_per_block < (size_t) 2) {
138 return 0; /* INTERNAL ERROR! */
143 al = allocate(sizeof *al);
147 al->atom_size = atom_size;
148 al->block_size = block_size;
149 al->allocate = allocate;
150 al->deallocate = deallocate;
153 al->atoms_per_block = atoms_per_block;
159 afs_atomlist_destroy(afs_atomlist * al)
164 for (cur = al->block_head; cur; cur = next) {
165 next = *(void **)((char *)cur + al->atoms_per_block * al->atom_size);
166 al->deallocate(cur, al->block_size);
168 al->deallocate(al, sizeof *al);
172 afs_atomlist_get(afs_atomlist * 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;
213 afs_atomlist_put(afs_atomlist * al, void *data)
215 *(void **)data = al->atom_head;
216 al->atom_head = data;