![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Early Linux] / linux / lib|
Return to malloc.c CVS log | Up to [Early Linux] / linux / lib |
1.1 root 1: /*
2: * malloc.c --- a general purpose kernel memory allocator for Linux.
3: *
4: * Written by Theodore Ts'o ([email protected]), 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:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.