1 /* $OpenBSD: kern_malloc.c,v 1.56 2003/12/28 16:35:46 tedu Exp $ */
2 /* $NetBSD: kern_malloc.c,v 1.15.4.2 1996/06/13 17:10:56 cgd Exp $ */
3
4 /*
5 * Copyright (c) 1987, 1991, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)kern_malloc.c 8.3 (Berkeley) 1/4/94
33 */
34
35 #include <sys/param.h>
36 #include <sys/proc.h>
37 #include <sys/kernel.h>
38 #include <sys/malloc.h>
39 #include <sys/systm.h>
40 #include <sys/sysctl.h>
41
42 #include <uvm/uvm_extern.h>
43
44 static struct vm_map_intrsafe kmem_map_store;
45 struct vm_map *kmem_map = NULL;
46
47 #ifdef NKMEMCLUSTERS
48 #error NKMEMCLUSTERS is obsolete; remove it from your kernel config file and use NKMEMPAGES instead or let the kernel auto-size
49 #endif
50
51 /*
52 * Default number of pages in kmem_map. We attempt to calculate this
53 * at run-time, but allow it to be either patched or set in the kernel
54 * config file.
55 */
56 #ifndef NKMEMPAGES
57 #define NKMEMPAGES 0
58 #endif
59 int nkmempages = NKMEMPAGES;
60
61 /*
62 * Defaults for lower- and upper-bounds for the kmem_map page count.
63 * Can be overridden by kernel config options.
64 */
65 #ifndef NKMEMPAGES_MIN
66 #define NKMEMPAGES_MIN NKMEMPAGES_MIN_DEFAULT
67 #endif
68
69 #ifndef NKMEMPAGES_MAX
70 #define NKMEMPAGES_MAX NKMEMPAGES_MAX_DEFAULT
71 #endif
72
73 struct kmembuckets bucket[MINBUCKET + 16];
74 struct kmemstats kmemstats[M_LAST];
75 struct kmemusage *kmemusage;
76 char *kmembase, *kmemlimit;
77 char buckstring[16 * sizeof("123456,")];
78 int buckstring_init = 0;
79 #if defined(KMEMSTATS) || defined(DIAGNOSTIC) || defined(FFS_SOFTUPDATES)
80 char *memname[] = INITKMEMNAMES;
81 char *memall = NULL;
82 extern struct lock sysctl_kmemlock;
83 #endif
84
85 #ifdef DIAGNOSTIC
86 /*
87 * This structure provides a set of masks to catch unaligned frees.
88 */
89 const long addrmask[] = { 0,
90 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
91 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
92 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
93 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
94 };
95
96 /*
97 * The WEIRD_ADDR is used as known text to copy into free objects so
98 * that modifications after frees can be detected.
99 */
100 #define WEIRD_ADDR ((unsigned) 0xdeadbeef)
101 #define MAX_COPY 32
102
103 /*
104 * Normally the freelist structure is used only to hold the list pointer
105 * for free objects. However, when running with diagnostics, the first
106 * 8 bytes of the structure is unused except for diagnostic information,
107 * and the free list pointer is at offset 8 in the structure. Since the
108 * first 8 bytes is the portion of the structure most often modified, this
109 * helps to detect memory reuse problems and avoid free list corruption.
110 */
111 struct freelist {
112 int32_t spare0;
113 int16_t type;
114 int16_t spare1;
115 caddr_t next;
116 };
117 #else /* !DIAGNOSTIC */
118 struct freelist {
119 caddr_t next;
120 };
121 #endif /* DIAGNOSTIC */
122
123 /*
124 * Allocate a block of memory
125 */
126 void *
malloc(size,type,flags)127 malloc(size, type, flags)
128 unsigned long size;
129 int type, flags;
130 {
131 register struct kmembuckets *kbp;
132 register struct kmemusage *kup;
133 register struct freelist *freep;
134 long indx, npg, allocsize;
135 int s;
136 caddr_t va, cp, savedlist;
137 #ifdef DIAGNOSTIC
138 int32_t *end, *lp;
139 int copysize;
140 char *savedtype;
141 #endif
142 #ifdef KMEMSTATS
143 register struct kmemstats *ksp = &kmemstats[type];
144
145 if (((unsigned long)type) >= M_LAST)
146 panic("malloc - bogus type");
147 #endif
148
149 #ifdef MALLOC_DEBUG
150 if (debug_malloc(size, type, flags, (void **)&va)) {
151 if ((flags & M_ZERO) && va != NULL)
152 memset(va, 0, size);
153 return ((void *) va);
154 }
155 #endif
156
157 if (size > 65535 * PAGE_SIZE)
158 panic("malloc: allocation too large");
159 indx = BUCKETINDX(size);
160 kbp = &bucket[indx];
161 s = splvm();
162 #ifdef KMEMSTATS
163 while (ksp->ks_memuse >= ksp->ks_limit) {
164 if (flags & M_NOWAIT) {
165 splx(s);
166 return ((void *) NULL);
167 }
168 if (ksp->ks_limblocks < 65535)
169 ksp->ks_limblocks++;
170 tsleep(ksp, PSWP+2, memname[type], 0);
171 }
172 ksp->ks_size |= 1 << indx;
173 #endif
174 #ifdef DIAGNOSTIC
175 copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY;
176 #endif
177 if (kbp->kb_next == NULL) {
178 kbp->kb_last = NULL;
179 if (size > MAXALLOCSAVE)
180 allocsize = round_page(size);
181 else
182 allocsize = 1 << indx;
183 npg = btoc(allocsize);
184 va = (caddr_t) uvm_km_kmemalloc(kmem_map, uvmexp.kmem_object,
185 (vsize_t)ctob(npg),
186 (flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0);
187 if (va == NULL) {
188 /*
189 * Kmem_malloc() can return NULL, even if it can
190 * wait, if there is no map space available, because
191 * it can't fix that problem. Neither can we,
192 * right now. (We should release pages which
193 * are completely free and which are in buckets
194 * with too many free elements.)
195 */
196 if ((flags & M_NOWAIT) == 0)
197 panic("malloc: out of space in kmem_map");
198 splx(s);
199 return ((void *) NULL);
200 }
201 #ifdef KMEMSTATS
202 kbp->kb_total += kbp->kb_elmpercl;
203 #endif
204 kup = btokup(va);
205 kup->ku_indx = indx;
206 if (allocsize > MAXALLOCSAVE) {
207 kup->ku_pagecnt = npg;
208 #ifdef KMEMSTATS
209 ksp->ks_memuse += allocsize;
210 #endif
211 goto out;
212 }
213 #ifdef KMEMSTATS
214 kup->ku_freecnt = kbp->kb_elmpercl;
215 kbp->kb_totalfree += kbp->kb_elmpercl;
216 #endif
217 /*
218 * Just in case we blocked while allocating memory,
219 * and someone else also allocated memory for this
220 * bucket, don't assume the list is still empty.
221 */
222 savedlist = kbp->kb_next;
223 kbp->kb_next = cp = va + (npg * PAGE_SIZE) - allocsize;
224 for (;;) {
225 freep = (struct freelist *)cp;
226 #ifdef DIAGNOSTIC
227 /*
228 * Copy in known text to detect modification
229 * after freeing.
230 */
231 end = (int32_t *)&cp[copysize];
232 for (lp = (int32_t *)cp; lp < end; lp++)
233 *lp = WEIRD_ADDR;
234 freep->type = M_FREE;
235 #endif /* DIAGNOSTIC */
236 if (cp <= va)
237 break;
238 cp -= allocsize;
239 freep->next = cp;
240 }
241 freep->next = savedlist;
242 if (kbp->kb_last == NULL)
243 kbp->kb_last = (caddr_t)freep;
244 }
245 va = kbp->kb_next;
246 kbp->kb_next = ((struct freelist *)va)->next;
247 #ifdef DIAGNOSTIC
248 freep = (struct freelist *)va;
249 savedtype = (unsigned)freep->type < M_LAST ?
250 memname[freep->type] : "???";
251 if (kbp->kb_next) {
252 int rv;
253 vaddr_t addr = (vaddr_t)kbp->kb_next;
254
255 vm_map_lock(kmem_map);
256 rv = uvm_map_checkprot(kmem_map, addr,
257 addr + sizeof(struct freelist), VM_PROT_WRITE);
258 vm_map_unlock(kmem_map);
259
260 if (!rv) {
261 printf("%s %ld of object %p size 0x%lx %s %s (invalid addr %p)\n",
262 "Data modified on freelist: word",
263 (int32_t *)&kbp->kb_next - (int32_t *)kbp, va, size,
264 "previous type", savedtype, kbp->kb_next);
265 kbp->kb_next = NULL;
266 }
267 }
268
269 /* Fill the fields that we've used with WEIRD_ADDR */
270 #if BYTE_ORDER == BIG_ENDIAN
271 freep->type = WEIRD_ADDR >> 16;
272 #endif
273 #if BYTE_ORDER == LITTLE_ENDIAN
274 freep->type = (short)WEIRD_ADDR;
275 #endif
276 end = (int32_t *)&freep->next +
277 (sizeof(freep->next) / sizeof(int32_t));
278 for (lp = (int32_t *)&freep->next; lp < end; lp++)
279 *lp = WEIRD_ADDR;
280
281 /* and check that the data hasn't been modified. */
282 end = (int32_t *)&va[copysize];
283 for (lp = (int32_t *)va; lp < end; lp++) {
284 if (*lp == WEIRD_ADDR)
285 continue;
286 printf("%s %ld of object %p size 0x%lx %s %s (0x%x != 0x%x)\n",
287 "Data modified on freelist: word", lp - (int32_t *)va,
288 va, size, "previous type", savedtype, *lp, WEIRD_ADDR);
289 break;
290 }
291
292 freep->spare0 = 0;
293 #endif /* DIAGNOSTIC */
294 #ifdef KMEMSTATS
295 kup = btokup(va);
296 if (kup->ku_indx != indx)
297 panic("malloc: wrong bucket");
298 if (kup->ku_freecnt == 0)
299 panic("malloc: lost data");
300 kup->ku_freecnt--;
301 kbp->kb_totalfree--;
302 ksp->ks_memuse += 1 << indx;
303 out:
304 kbp->kb_calls++;
305 ksp->ks_inuse++;
306 ksp->ks_calls++;
307 if (ksp->ks_memuse > ksp->ks_maxused)
308 ksp->ks_maxused = ksp->ks_memuse;
309 #else
310 out:
311 #endif
312 splx(s);
313
314 if ((flags & M_ZERO) && va != NULL)
315 memset(va, 0, size);
316 return ((void *) va);
317 }
318
319 /*
320 * Free a block of memory allocated by malloc.
321 */
322 void
free(addr,type)323 free(addr, type)
324 void *addr;
325 int type;
326 {
327 register struct kmembuckets *kbp;
328 register struct kmemusage *kup;
329 register struct freelist *freep;
330 long size;
331 int s;
332 #ifdef DIAGNOSTIC
333 caddr_t cp;
334 int32_t *end, *lp;
335 long alloc, copysize;
336 #endif
337 #ifdef KMEMSTATS
338 register struct kmemstats *ksp = &kmemstats[type];
339 #endif
340
341 #ifdef MALLOC_DEBUG
342 if (debug_free(addr, type))
343 return;
344 #endif
345
346 #ifdef DIAGNOSTIC
347 if (addr < (void *)kmembase || addr >= (void *)kmemlimit)
348 panic("free: non-malloced addr %p type %s", addr,
349 memname[type]);
350 #endif
351
352 kup = btokup(addr);
353 size = 1 << kup->ku_indx;
354 kbp = &bucket[kup->ku_indx];
355 s = splvm();
356 #ifdef DIAGNOSTIC
357 /*
358 * Check for returns of data that do not point to the
359 * beginning of the allocation.
360 */
361 if (size > PAGE_SIZE)
362 alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
363 else
364 alloc = addrmask[kup->ku_indx];
365 if (((u_long)addr & alloc) != 0)
366 panic("free: unaligned addr %p, size %ld, type %s, mask %ld",
367 addr, size, memname[type], alloc);
368 #endif /* DIAGNOSTIC */
369 if (size > MAXALLOCSAVE) {
370 uvm_km_free(kmem_map, (vaddr_t)addr, ctob(kup->ku_pagecnt));
371 #ifdef KMEMSTATS
372 size = kup->ku_pagecnt << PGSHIFT;
373 ksp->ks_memuse -= size;
374 kup->ku_indx = 0;
375 kup->ku_pagecnt = 0;
376 if (ksp->ks_memuse + size >= ksp->ks_limit &&
377 ksp->ks_memuse < ksp->ks_limit)
378 wakeup(ksp);
379 ksp->ks_inuse--;
380 kbp->kb_total -= 1;
381 #endif
382 splx(s);
383 return;
384 }
385 freep = (struct freelist *)addr;
386 #ifdef DIAGNOSTIC
387 /*
388 * Check for multiple frees. Use a quick check to see if
389 * it looks free before laboriously searching the freelist.
390 */
391 if (freep->spare0 == WEIRD_ADDR) {
392 for (cp = kbp->kb_next; cp;
393 cp = ((struct freelist *)cp)->next) {
394 if (addr != cp)
395 continue;
396 printf("multiply freed item %p\n", addr);
397 panic("free: duplicated free");
398 }
399 }
400 /*
401 * Copy in known text to detect modification after freeing
402 * and to make it look free. Also, save the type being freed
403 * so we can list likely culprit if modification is detected
404 * when the object is reallocated.
405 */
406 copysize = size < MAX_COPY ? size : MAX_COPY;
407 end = (int32_t *)&((caddr_t)addr)[copysize];
408 for (lp = (int32_t *)addr; lp < end; lp++)
409 *lp = WEIRD_ADDR;
410 freep->type = type;
411 #endif /* DIAGNOSTIC */
412 #ifdef KMEMSTATS
413 kup->ku_freecnt++;
414 if (kup->ku_freecnt >= kbp->kb_elmpercl) {
415 if (kup->ku_freecnt > kbp->kb_elmpercl)
416 panic("free: multiple frees");
417 else if (kbp->kb_totalfree > kbp->kb_highwat)
418 kbp->kb_couldfree++;
419 }
420 kbp->kb_totalfree++;
421 ksp->ks_memuse -= size;
422 if (ksp->ks_memuse + size >= ksp->ks_limit &&
423 ksp->ks_memuse < ksp->ks_limit)
424 wakeup(ksp);
425 ksp->ks_inuse--;
426 #endif
427 if (kbp->kb_next == NULL)
428 kbp->kb_next = addr;
429 else
430 ((struct freelist *)kbp->kb_last)->next = addr;
431 freep->next = NULL;
432 kbp->kb_last = addr;
433 splx(s);
434 }
435
436 /*
437 * Compute the number of pages that kmem_map will map, that is,
438 * the size of the kernel malloc arena.
439 */
440 void
kmeminit_nkmempages()441 kmeminit_nkmempages()
442 {
443 int npages;
444
445 if (nkmempages != 0) {
446 /*
447 * It's already been set (by us being here before, or
448 * by patching or kernel config options), bail out now.
449 */
450 return;
451 }
452
453 /*
454 * We use the following (simple) formula:
455 *
456 * - Starting point is physical memory / 4.
457 *
458 * - Clamp it down to NKMEMPAGES_MAX.
459 *
460 * - Round it up to NKMEMPAGES_MIN.
461 */
462 npages = physmem / 4;
463
464 if (npages > NKMEMPAGES_MAX)
465 npages = NKMEMPAGES_MAX;
466
467 if (npages < NKMEMPAGES_MIN)
468 npages = NKMEMPAGES_MIN;
469
470 nkmempages = npages;
471 }
472
473 /*
474 * Initialize the kernel memory allocator
475 */
476 void
kmeminit()477 kmeminit()
478 {
479 vaddr_t base, limit;
480 #ifdef KMEMSTATS
481 long indx;
482 #endif
483
484 #ifdef DIAGNOSTIC
485 if (sizeof(struct freelist) > (1 << MINBUCKET))
486 panic("kmeminit: minbucket too small/struct freelist too big");
487 #endif
488
489 /*
490 * Compute the number of kmem_map pages, if we have not
491 * done so already.
492 */
493 kmeminit_nkmempages();
494 base = vm_map_min(kernel_map);
495 kmem_map = uvm_km_suballoc(kernel_map, &base, &limit,
496 (vsize_t)(nkmempages * PAGE_SIZE), VM_MAP_INTRSAFE, FALSE,
497 &kmem_map_store.vmi_map);
498 kmembase = (char *)base;
499 kmemlimit = (char *)limit;
500 kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map,
501 (vsize_t)(nkmempages * sizeof(struct kmemusage)));
502 #ifdef KMEMSTATS
503 for (indx = 0; indx < MINBUCKET + 16; indx++) {
504 if (1 << indx >= PAGE_SIZE)
505 bucket[indx].kb_elmpercl = 1;
506 else
507 bucket[indx].kb_elmpercl = PAGE_SIZE / (1 << indx);
508 bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl;
509 }
510 for (indx = 0; indx < M_LAST; indx++)
511 kmemstats[indx].ks_limit = nkmempages * PAGE_SIZE * 6 / 10;
512 #endif
513 #ifdef MALLOC_DEBUG
514 debug_malloc_init();
515 #endif
516 }
517
518 /*
519 * Return kernel malloc statistics information.
520 */
521 int
sysctl_malloc(name,namelen,oldp,oldlenp,newp,newlen,p)522 sysctl_malloc(name, namelen, oldp, oldlenp, newp, newlen, p)
523 int *name;
524 u_int namelen;
525 void *oldp;
526 size_t *oldlenp;
527 void *newp;
528 size_t newlen;
529 struct proc *p;
530 {
531 struct kmembuckets kb;
532 int i, siz;
533
534 if (namelen != 2 && name[0] != KERN_MALLOC_BUCKETS &&
535 name[0] != KERN_MALLOC_KMEMNAMES)
536 return (ENOTDIR); /* overloaded */
537
538 switch (name[0]) {
539 case KERN_MALLOC_BUCKETS:
540 /* Initialize the first time */
541 if (buckstring_init == 0) {
542 buckstring_init = 1;
543 bzero(buckstring, sizeof(buckstring));
544 for (siz = 0, i = MINBUCKET; i < MINBUCKET + 16; i++) {
545 snprintf(buckstring + siz,
546 sizeof buckstring - siz,
547 "%d,", (u_int)(1<<i));
548 siz += strlen(buckstring + siz);
549 }
550 /* Remove trailing comma */
551 if (siz)
552 buckstring[siz - 1] = '\0';
553 }
554 return (sysctl_rdstring(oldp, oldlenp, newp, buckstring));
555
556 case KERN_MALLOC_BUCKET:
557 bcopy(&bucket[BUCKETINDX(name[1])], &kb, sizeof(kb));
558 kb.kb_next = kb.kb_last = 0;
559 return (sysctl_rdstruct(oldp, oldlenp, newp, &kb, sizeof(kb)));
560 case KERN_MALLOC_KMEMSTATS:
561 #ifdef KMEMSTATS
562 if ((name[1] < 0) || (name[1] >= M_LAST))
563 return (EINVAL);
564 return (sysctl_rdstruct(oldp, oldlenp, newp,
565 &kmemstats[name[1]], sizeof(struct kmemstats)));
566 #else
567 return (EOPNOTSUPP);
568 #endif
569 case KERN_MALLOC_KMEMNAMES:
570 #if defined(KMEMSTATS) || defined(DIAGNOSTIC) || defined(FFS_SOFTUPDATES)
571 if (memall == NULL) {
572 int totlen;
573
574 i = lockmgr(&sysctl_kmemlock, LK_EXCLUSIVE, NULL, p);
575 if (i)
576 return (i);
577
578 /* Figure out how large a buffer we need */
579 for (totlen = 0, i = 0; i < M_LAST; i++) {
580 if (memname[i])
581 totlen += strlen(memname[i]);
582 totlen++;
583 }
584 memall = malloc(totlen + M_LAST, M_SYSCTL,
585 M_WAITOK|M_ZERO);
586 for (siz = 0, i = 0; i < M_LAST; i++) {
587 snprintf(memall + siz,
588 totlen + M_LAST - siz,
589 "%s,", memname[i] ? memname[i] : "");
590 siz += strlen(memall + siz);
591 }
592 /* Remove trailing comma */
593 if (siz)
594 memall[siz - 1] = '\0';
595
596 /* Now, convert all spaces to underscores */
597 for (i = 0; i < totlen; i++)
598 if (memall[i] == ' ')
599 memall[i] = '_';
600 lockmgr(&sysctl_kmemlock, LK_RELEASE, NULL, p);
601 }
602 return (sysctl_rdstring(oldp, oldlenp, newp, memall));
603 #else
604 return (EOPNOTSUPP);
605 #endif
606 default:
607 return (EOPNOTSUPP);
608 }
609 /* NOTREACHED */
610 }
611
612 /*
613 * Round up a size to how much malloc would actually allocate.
614 */
615 size_t
malloc_roundup(size_t sz)616 malloc_roundup(size_t sz)
617 {
618 if (sz > MAXALLOCSAVE)
619 return round_page(sz);
620
621 return (1 << BUCKETINDX(sz));
622 }
623