1 /*
2 * malloc.c --- a general purpose kernel memory allocator for Linux.
3 *
4 * Written by Theodore Ts'o (tytso@mit.edu), 11/29/91
5 *
6 * This routine is written to be as fast as possible, so that it
7 * can be called from the interrupt level.
8 *
9 * Limitations: maximum size of memory we can allocate using this routine
10 * is 4k, the size of a page in Linux.
11 *
12 * The general game plan is that each page (called a bucket) will only hold
13 * objects of a given size. When all of the object on a page are released,
14 * the page can be returned to the general free pool. When malloc() is
15 * called, it looks for the smallest bucket size which will fulfill its
16 * request, and allocate a piece of memory from that bucket pool.
17 *
18 * Each bucket has as its control block a bucket descriptor which keeps
19 * track of how many objects are in use on that page, and the free list
20 * for that page. Like the buckets themselves, bucket descriptors are
21 * stored on pages requested from get_free_page(). However, unlike buckets,
22 * pages devoted to bucket descriptor pages are never released back to the
23 * system. Fortunately, a system should probably only need 1 or 2 bucket
24 * descriptor pages, since a page can hold 256 bucket descriptors (which
25 * corresponds to 1 megabyte worth of bucket pages.) If the kernel is using
26 * that much allocated memory, it's probably doing something wrong. :-)
27 *
28 * Note: malloc() and free() both call get_free_page() and free_page()
29 * in sections of code where interrupts are turned off, to allow
30 * malloc() and free() to be safely called from an interrupt routine.
31 * (We will probably need this functionality when networking code,
32 * particularily things like NFS, is added to Linux.) However, this
33 * presumes that get_free_page() and free_page() are interrupt-level
34 * safe, which they may not be once paging is added. If this is the
35 * case, we will need to modify malloc() to keep a few unused pages
36 * "pre-allocated" so that it can safely draw upon those pages if
37 * it is called from an interrupt routine.
38 *
39 * Another concern is that get_free_page() should not sleep; if it
40 * does, the code is carefully ordered so as to avoid any race
41 * conditions. The catch is that if malloc() is called re-entrantly,
42 * there is a chance that unecessary pages will be grabbed from the
43 * system. Except for the pages for the bucket descriptor page, the
44 * extra pages will eventually get released back to the system, though,
45 * so it isn't all that bad.
46 */
47
48 #include <linux/kernel.h>
49 #include <linux/mm.h>
50 #include <asm/system.h>
51
52 struct bucket_desc { /* 16 bytes */
53 void *page;
54 struct bucket_desc *next;
55 void *freeptr;
56 unsigned short refcnt;
57 unsigned short bucket_size;
58 };
59
60 struct _bucket_dir { /* 8 bytes */
61 int size;
62 struct bucket_desc *chain;
63 };
64
65 /*
66 * The following is the where we store a pointer to the first bucket
67 * descriptor for a given size.
68 *
69 * If it turns out that the Linux kernel allocates a lot of objects of a
70 * specific size, then we may want to add that specific size to this list,
71 * since that will allow the memory to be allocated more efficiently.
72 * However, since an entire page must be dedicated to each specific size
73 * on this list, some amount of temperance must be exercised here.
74 *
75 * Note that this list *must* be kept in order.
76 */
77 struct _bucket_dir bucket_dir[] = {
78 { 16, (struct bucket_desc *) 0},
79 { 32, (struct bucket_desc *) 0},
80 { 64, (struct bucket_desc *) 0},
81 { 128, (struct bucket_desc *) 0},
82 { 256, (struct bucket_desc *) 0},
83 { 512, (struct bucket_desc *) 0},
84 { 1024, (struct bucket_desc *) 0},
85 { 2048, (struct bucket_desc *) 0},
86 { 4096, (struct bucket_desc *) 0},
87 { 0, (struct bucket_desc *) 0}}; /* End of list marker */
88
89 /*
90 * This contains a linked list of free bucket descriptor blocks
91 */
92 struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;
93
94 /*
95 * This routine initializes a bucket description page.
96 */
97 static inline void init_bucket_desc()
98 {
99 struct bucket_desc *bdesc, *first;
100 int i;
101
102 first = bdesc = (struct bucket_desc *) get_free_page();
103 if (!bdesc)
104 panic("Out of memory in init_bucket_desc()");
105 for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
106 bdesc->next = bdesc+1;
107 bdesc++;
108 }
109 /*
110 * This is done last, to avoid race conditions in case
111 * get_free_page() sleeps and this routine gets called again....
112 */
113 bdesc->next = free_bucket_desc;
114 free_bucket_desc = first;
115 }
116
117 void *malloc(unsigned int len)
118 {
119 struct _bucket_dir *bdir;
120 struct bucket_desc *bdesc;
121 void *retval;
122
123 /*
124 * First we search the bucket_dir to find the right bucket change
125 * for this request.
126 */
127 for (bdir = bucket_dir; bdir->size; bdir++)
128 if (bdir->size >= len)
129 break;
130 if (!bdir->size) {
131 printk("malloc called with impossibly large argument (%d)\n",
132 len);
133 panic("malloc: bad arg");
134 }
135 /*
136 * Now we search for a bucket descriptor which has free space
137 */
138 cli(); /* Avoid race conditions */
139 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next)
140 if (bdesc->freeptr)
141 break;
142 /*
143 * If we didn't find a bucket with free space, then we'll
144 * allocate a new one.
145 */
146 if (!bdesc) {
147 char *cp;
148 int i;
149
150 if (!free_bucket_desc)
151 init_bucket_desc();
152 bdesc = free_bucket_desc;
153 free_bucket_desc = bdesc->next;
154 bdesc->refcnt = 0;
155 bdesc->bucket_size = bdir->size;
156 bdesc->page = bdesc->freeptr = (void *) cp = get_free_page();
157 if (!cp)
158 panic("Out of memory in kernel malloc()");
159 /* Set up the chain of free objects */
160 for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
161 *((char **) cp) = cp + bdir->size;
162 cp += bdir->size;
163 }
164 *((char **) cp) = 0;
165 bdesc->next = bdir->chain; /* OK, link it in! */
166 bdir->chain = bdesc;
167 }
168 retval = (void *) bdesc->freeptr;
169 bdesc->freeptr = *((void **) retval);
170 bdesc->refcnt++;
171 sti(); /* OK, we're safe again */
172 return(retval);
173 }
174
175 /*
176 * Here is the free routine. If you know the size of the object that you
177 * are freeing, then free_s() will use that information to speed up the
178 * search for the bucket descriptor.
179 *
180 * We will #define a macro so that "free(x)" is becomes "free_s(x, 0)"
181 */
182 void free_s(void *obj, int size)
183 {
184 void *page;
185 struct _bucket_dir *bdir;
186 struct bucket_desc *bdesc, *prev;
187
188 /* Calculate what page this object lives in */
189 page = (void *) ((unsigned long) obj & 0xfffff000);
190 /* Now search the buckets looking for that page */
191 for (bdir = bucket_dir; bdir->size; bdir++) {
192 prev = 0;
193 /* If size is zero then this conditional is always false */
194 if (bdir->size < size)
195 continue;
196 for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
197 if (bdesc->page == page)
198 goto found;
199 prev = bdesc;
200 }
201 }
202 panic("Bad address passed to kernel free_s()");
203 found:
204 cli(); /* To avoid race conditions */
205 *((void **)obj) = bdesc->freeptr;
206 bdesc->freeptr = obj;
207 bdesc->refcnt--;
208 if (bdesc->refcnt == 0) {
209 /*
210 * We need to make sure that prev is still accurate. It
211 * may not be, if someone rudely interrupted us....
212 */
213 if ((prev && (prev->next != bdesc)) ||
214 (!prev && (bdir->chain != bdesc)))
215 for (prev = bdir->chain; prev; prev = prev->next)
216 if (prev->next == bdesc)
217 break;
218 if (prev)
219 prev->next = bdesc->next;
220 else {
221 if (bdir->chain != bdesc)
222 panic("malloc bucket chains corrupted");
223 bdir->chain = bdesc->next;
224 }
225 free_page((unsigned long) bdesc->page);
226 bdesc->next = free_bucket_desc;
227 free_bucket_desc = bdesc;
228 }
229 sti();
230 return;
231 }
232
233
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.