| 1 | /* |
| 2 | * Copyright 2000, International Business Machines Corporation and others. |
| 3 | * All Rights Reserved. |
| 4 | * |
| 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 |
| 8 | */ |
| 9 | |
| 10 | #include <afsconfig.h> |
| 11 | #include <afs/param.h> |
| 12 | |
| 13 | |
| 14 | #ifdef KERNEL |
| 15 | #include "afs_atomlist.h" |
| 16 | #else /* KERNEL */ |
| 17 | #include "afs_atomlist.h" |
| 18 | #endif /* KERNEL */ |
| 19 | |
| 20 | /* |
| 21 | * The afs_atomlist abstract data type is for efficiently allocating |
| 22 | * space for small structures. |
| 23 | * |
| 24 | * The atoms in an afs_atomlist are allocated in blocks. The blocks |
| 25 | * are chained together so that they can be freed when the afs_atomlist |
| 26 | * is destroyed. When a new block is allocated, its atoms are chained |
| 27 | * together and added to the free list of atoms. |
| 28 | * |
| 29 | * If the requested atom size is smaller than the size of a pointer, |
| 30 | * afs_atomlist_create() silently increases the atom size. If |
| 31 | * the atom size would result in incorrectly aligned pointers, |
| 32 | * afs_atomlist_create() silently increases the atom size as necessary. |
| 33 | * |
| 34 | * A block of atoms is organized as follows. |
| 35 | * |
| 36 | * --------------------------------------------------------------- |
| 37 | * | atom | atom | atom | ... | atom | nextblock | wasted space* | |
| 38 | * --------------------------------------------------------------- |
| 39 | * \____ atoms_per_block atoms ______/ |
| 40 | * |
| 41 | * (*) A block may or may not contain wasted space at the end. The |
| 42 | * amount of wasted space depends on the size of a block, the size of an |
| 43 | * atom, and the size of the pointer to the next block. For instance, |
| 44 | * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4 |
| 45 | * bytes, there is no wasted space in a block. |
| 46 | * |
| 47 | * The pointer to the next block is stored AFTER all the atoms in the |
| 48 | * block. Here's why. |
| 49 | * |
| 50 | * If we put the pointer to the next block before the atoms, |
| 51 | * followed immediately by the atoms, we would be assuming that the |
| 52 | * atoms could be aligned on a pointer boundary. |
| 53 | * |
| 54 | * If we tried to solve the alignment problem by allocating an entire |
| 55 | * atom for the pointer to the next block, we might waste space |
| 56 | * gratuitously. Say a block is 4096 bytes, an atom is 24 bytes, and a |
| 57 | * pointer is 8 bytes. In this case a block can hold 170 atoms, with 16 |
| 58 | * bytes left over. This isn't enough space for another atom, but it is |
| 59 | * enough space for the pointer to the next block. There is no need to |
| 60 | * use one of the atoms to store the pointer to the next block. |
| 61 | * |
| 62 | * So, we store the pointer to the next block after the end of the atoms |
| 63 | * in the block. In the worst case, the block size is an exact multiple |
| 64 | * of the atom size, and we waste an entire atom to store the pointer to |
| 65 | * the next block. But we hope it is more typical that there is enough |
| 66 | * extra space after the atoms to store the pointer to the next block. |
| 67 | * |
| 68 | * A more sophisticated scheme would keep the pointers to the atom |
| 69 | * blocks in a separate list of blocks. It would eliminate the |
| 70 | * fragmentation of the atom blocks in the case where the block size |
| 71 | * is a multiple of the atom size. However, it is more complicated to |
| 72 | * understand and to implement, so I chose not to do it at this time. |
| 73 | * If fragmentation turns out to be a serious enough issue, we can |
| 74 | * change the afs_atomlist implementation without affecting its users. |
| 75 | */ |
| 76 | |
| 77 | struct afs_atomlist { |
| 78 | size_t atom_size; |
| 79 | size_t block_size; |
| 80 | size_t atoms_per_block; |
| 81 | void *(*allocate) (size_t n); |
| 82 | void (*deallocate) (void *p, size_t n); |
| 83 | void *atom_head; /* pointer to head of atom free list */ |
| 84 | void *block_head; /* pointer to block list */ |
| 85 | }; |
| 86 | |
| 87 | afs_atomlist * |
| 88 | afs_atomlist_create(size_t atom_size, size_t block_size, |
| 89 | void *(*allocate) (size_t n) |
| 90 | , void (*deallocate) (void *p, size_t n) |
| 91 | ) |
| 92 | { |
| 93 | afs_atomlist *al; |
| 94 | size_t atoms_per_block; |
| 95 | size_t extra_space; |
| 96 | |
| 97 | /* |
| 98 | * Atoms must be at least as big as a pointer in order for |
| 99 | * our implementation of the atom free list to work. |
| 100 | */ |
| 101 | if (atom_size < sizeof(void *)) { |
| 102 | atom_size = sizeof(void *); |
| 103 | } |
| 104 | |
| 105 | /* |
| 106 | * Atoms must be a multiple of the size of a pointer |
| 107 | * so that the pointers in the atom free list will be |
| 108 | * properly aligned. |
| 109 | */ |
| 110 | if (atom_size % sizeof(void *) != (size_t) 0) { |
| 111 | size_t pad = sizeof(void *) - (atom_size % sizeof(void *)); |
| 112 | atom_size += pad; |
| 113 | } |
| 114 | |
| 115 | /* |
| 116 | * Blocks are the unit of memory allocation. |
| 117 | * |
| 118 | * 1) Atoms are allocated out of blocks. |
| 119 | * |
| 120 | * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *) |
| 121 | * boundary, are used to chain together the blocks so that they can |
| 122 | * be freed later. This reduces the space in each block for atoms. |
| 123 | * It is intended that atoms should be small relative to the size of |
| 124 | * a block, so this should not be a problem. |
| 125 | * |
| 126 | * At a minimum, a block must be big enough for one atom and |
| 127 | * a pointer to the next block. |
| 128 | */ |
| 129 | if (block_size < atom_size + sizeof(void *)) |
| 130 | return 0; |
| 131 | |
| 132 | atoms_per_block = block_size / atom_size; |
| 133 | extra_space = block_size - (atoms_per_block * atom_size); |
| 134 | if (extra_space < sizeof(void *)) { |
| 135 | if (atoms_per_block < (size_t) 2) { |
| 136 | return 0; /* INTERNAL ERROR! */ |
| 137 | } |
| 138 | atoms_per_block--; |
| 139 | } |
| 140 | |
| 141 | al = allocate(sizeof *al); |
| 142 | if (!al) |
| 143 | return 0; |
| 144 | |
| 145 | al->atom_size = atom_size; |
| 146 | al->block_size = block_size; |
| 147 | al->allocate = allocate; |
| 148 | al->deallocate = deallocate; |
| 149 | al->atom_head = 0; |
| 150 | al->block_head = 0; |
| 151 | al->atoms_per_block = atoms_per_block; |
| 152 | |
| 153 | return al; |
| 154 | } |
| 155 | |
| 156 | void |
| 157 | afs_atomlist_destroy(afs_atomlist * al) |
| 158 | { |
| 159 | void *cur; |
| 160 | void *next; |
| 161 | |
| 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); |
| 165 | } |
| 166 | al->deallocate(al, sizeof *al); |
| 167 | } |
| 168 | |
| 169 | void * |
| 170 | afs_atomlist_get(afs_atomlist * al) |
| 171 | { |
| 172 | void *data; |
| 173 | |
| 174 | /* allocate a new block if necessary */ |
| 175 | if (!al->atom_head) { |
| 176 | void *block; |
| 177 | void *p; |
| 178 | size_t i; |
| 179 | |
| 180 | block = al->allocate(al->block_size); |
| 181 | if (!block) { |
| 182 | return 0; |
| 183 | } |
| 184 | |
| 185 | /* add this block to the chain of allocated blocks */ |
| 186 | *(void **)((char *)block + al->atoms_per_block * al->atom_size) = |
| 187 | al->block_head; |
| 188 | al->block_head = block; |
| 189 | |
| 190 | /* add this block's atoms to the atom free list */ |
| 191 | p = block; |
| 192 | for (i = 0; i + 1 < al->atoms_per_block; i++) { |
| 193 | *(void **)p = (char *)p + al->atom_size; |
| 194 | p = (char *)p + al->atom_size; |
| 195 | } |
| 196 | *(void **)p = 0; |
| 197 | al->atom_head = block; |
| 198 | } |
| 199 | |
| 200 | if (!al->atom_head) { |
| 201 | return 0; /* INTERNAL ERROR */ |
| 202 | } |
| 203 | |
| 204 | data = al->atom_head; |
| 205 | al->atom_head = *(void **)data; |
| 206 | |
| 207 | return data; |
| 208 | } |
| 209 | |
| 210 | void |
| 211 | afs_atomlist_put(afs_atomlist * al, void *data) |
| 212 | { |
| 213 | *(void **)data = al->atom_head; |
| 214 | al->atom_head = data; |
| 215 | } |