1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #include "primpl.h"
7
8 /*
9 ** We override malloc etc. on any platform which has preemption +
10 ** nspr20 user level threads. When we're debugging, we can make our
11 ** version of malloc fail occasionally.
12 */
13 #ifdef _PR_OVERRIDE_MALLOC
14
15 /*
16 ** Thread safe version of malloc, calloc, realloc, free
17 */
18 #include <stdarg.h>
19
20 #ifdef DEBUG
21 #define SANITY
22 #define EXTRA_SANITY
23 #else
24 #undef SANITY
25 #undef EXTRA_SANITY
26 #endif
27
28 /* Forward decls */
29 void *_PR_UnlockedMalloc(size_t size);
30 void _PR_UnlockedFree(void *ptr);
31 void *_PR_UnlockedRealloc(void *ptr, size_t size);
32 void *_PR_UnlockedCalloc(size_t n, size_t elsize);
33
34 /************************************************************************/
35
36 /*
37 * ----------------------------------------------------------------------------
38 * "THE BEER-WARE LICENSE" (Revision 42):
39 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
40 * can do whatever you want with this stuff. If we meet some day, and you think
41 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
42 * ----------------------------------------------------------------------------
43 *
44 */
45
46 /*
47 * Defining SANITY will enable some checks which will tell you if the users
48 * program did botch something
49 */
50
51 /*
52 * Defining EXTRA_SANITY will enable some checks which are mostly related
53 * to internal conditions in malloc.c
54 */
55
56 /*
57 * Very verbose progress on stdout...
58 */
59 #if 0
60 # define TRACE(foo) printf foo
61 static int malloc_event;
62 #else
63 # define TRACE(foo)
64 #endif
65
66 /* XXX Pick a number, any number */
67 # define malloc_pagesize 4096UL
68 # define malloc_pageshift 12UL
69
70 #ifdef XP_UNIX
71 #include <stdio.h>
72 #include <stdlib.h>
73 #include <unistd.h>
74 #include <string.h>
75 #include <errno.h>
76 #include <sys/types.h>
77 #include <sys/mman.h>
78 #endif
79
80 /*
81 * This structure describes a page's worth of chunks.
82 */
83
84 struct pginfo {
85 struct pginfo *next; /* next on the free list */
86 char *page; /* Pointer to the page */
87 u_short size; /* size of this page's chunks */
88 u_short shift; /* How far to shift for this size chunks */
89 u_short free; /* How many free chunks */
90 u_short total; /* How many chunk */
91 u_long bits[1]; /* Which chunks are free */
92 };
93
94 struct pgfree {
95 struct pgfree *next; /* next run of free pages */
96 struct pgfree *prev; /* prev run of free pages */
97 char *page; /* pointer to free pages */
98 char *end; /* pointer to end of free pages */
99 u_long size; /* number of bytes free */
100 };
101
102 /*
103 * How many bits per u_long in the bitmap.
104 * Change only if not 8 bits/byte
105 */
106 #define MALLOC_BITS (8*sizeof(u_long))
107
108 /*
109 * Magic values to put in the page_directory
110 */
111 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
112 #define MALLOC_FREE ((struct pginfo*) 1)
113 #define MALLOC_FIRST ((struct pginfo*) 2)
114 #define MALLOC_FOLLOW ((struct pginfo*) 3)
115 #define MALLOC_MAGIC ((struct pginfo*) 4)
116
117 /*
118 * Set to one when malloc_init has been called
119 */
120 static unsigned initialized;
121
122 /*
123 * The size of a page.
124 * Must be a integral multiplum of the granularity of mmap(2).
125 * Your toes will curl if it isn't a power of two
126 */
127 #define malloc_pagemask ((malloc_pagesize)-1)
128
129 /*
130 * The size of the largest chunk.
131 * Half a page.
132 */
133 #define malloc_maxsize ((malloc_pagesize)>>1)
134
135 /*
136 * malloc_pagesize == 1 << malloc_pageshift
137 */
138 #ifndef malloc_pageshift
139 static unsigned malloc_pageshift;
140 #endif /* malloc_pageshift */
141
142 /*
143 * The smallest allocation we bother about.
144 * Must be power of two
145 */
146 #ifndef malloc_minsize
147 static unsigned malloc_minsize;
148 #endif /* malloc_minsize */
149
150 /*
151 * The largest chunk we care about.
152 * Must be smaller than pagesize
153 * Must be power of two
154 */
155 #ifndef malloc_maxsize
156 static unsigned malloc_maxsize;
157 #endif /* malloc_maxsize */
158
159 #ifndef malloc_cache
160 static unsigned malloc_cache;
161 #endif /* malloc_cache */
162
163 /*
164 * The offset from pagenumber to index into the page directory
165 */
166 static u_long malloc_origo;
167
168 /*
169 * The last index in the page directory we care about
170 */
171 static u_long last_index;
172
173 /*
174 * Pointer to page directory.
175 * Allocated "as if with" malloc
176 */
177 static struct pginfo **page_dir;
178
179 /*
180 * How many slots in the page directory
181 */
182 static unsigned malloc_ninfo;
183
184 /*
185 * Free pages line up here
186 */
187 static struct pgfree free_list;
188
189 /*
190 * Abort() if we fail to get VM ?
191 */
192 static int malloc_abort;
193
194 #ifdef SANITY
195 /*
196 * Are we trying to die ?
197 */
198 static int suicide;
199 #endif
200
201 /*
202 * dump statistics
203 */
204 static int malloc_stats;
205
206 /*
207 * always realloc ?
208 */
209 static int malloc_realloc;
210
211 /*
212 * my last break.
213 */
214 static void *malloc_brk;
215
216 /*
217 * one location cache for free-list holders
218 */
219 static struct pgfree *px;
220
221 static int set_pgdir(void *ptr, struct pginfo *info);
222 static int extend_page_directory(u_long index);
223
224 #ifdef SANITY
225 void
malloc_dump(FILE * fd)226 malloc_dump(FILE *fd)
227 {
228 struct pginfo **pd;
229 struct pgfree *pf;
230 int j;
231
232 pd = page_dir;
233
234 /* print out all the pages */
235 for(j=0; j<=last_index; j++) {
236 fprintf(fd,"%08lx %5d ",(j+malloc_origo) << malloc_pageshift,j);
237 if (pd[j] == MALLOC_NOT_MINE) {
238 for(j++; j<=last_index && pd[j] == MALLOC_NOT_MINE; j++)
239 ;
240 j--;
241 fprintf(fd,".. %5d not mine\n", j);
242 } else if (pd[j] == MALLOC_FREE) {
243 for(j++; j<=last_index && pd[j] == MALLOC_FREE; j++)
244 ;
245 j--;
246 fprintf(fd,".. %5d free\n", j);
247 } else if (pd[j] == MALLOC_FIRST) {
248 for(j++; j<=last_index && pd[j] == MALLOC_FOLLOW; j++)
249 ;
250 j--;
251 fprintf(fd,".. %5d in use\n", j);
252 } else if (pd[j] < MALLOC_MAGIC) {
253 fprintf(fd,"(%p)\n", pd[j]);
254 } else {
255 fprintf(fd,"%p %d (of %d) x %d @ %p --> %p\n",
256 pd[j],pd[j]->free, pd[j]->total,
257 pd[j]->size, pd[j]->page, pd[j]->next);
258 }
259 }
260
261 for(pf=free_list.next; pf; pf=pf->next) {
262 fprintf(fd,"Free: @%p [%p...%p[ %ld ->%p <-%p\n",
263 pf,pf->page,pf->end,pf->size,pf->prev,pf->next);
264 if (pf == pf->next) {
265 fprintf(fd,"Free_list loops.\n");
266 break;
267 }
268 }
269
270 /* print out various info */
271 fprintf(fd,"Minsize\t%d\n",malloc_minsize);
272 fprintf(fd,"Maxsize\t%ld\n",malloc_maxsize);
273 fprintf(fd,"Pagesize\t%ld\n",malloc_pagesize);
274 fprintf(fd,"Pageshift\t%ld\n",malloc_pageshift);
275 fprintf(fd,"FirstPage\t%ld\n",malloc_origo);
276 fprintf(fd,"LastPage\t%ld %lx\n",last_index+malloc_pageshift,
277 (last_index + malloc_pageshift) << malloc_pageshift);
278 fprintf(fd,"Break\t%ld\n",(u_long)sbrk(0) >> malloc_pageshift);
279 }
280
wrterror(char * fmt,...)281 static void wrterror(char *fmt, ...)
282 {
283 char *q = "malloc() error: ";
284 char buf[100];
285 va_list ap;
286
287 suicide = 1;
288
289 va_start(ap, fmt);
290 PR_vsnprintf(buf, sizeof(buf), fmt, ap);
291 va_end(ap);
292 fputs(q, stderr);
293 fputs(buf, stderr);
294
295 malloc_dump(stderr);
296 PR_Abort();
297 }
298
wrtwarning(char * fmt,...)299 static void wrtwarning(char *fmt, ...)
300 {
301 char *q = "malloc() warning: ";
302 char buf[100];
303 va_list ap;
304
305 va_start(ap, fmt);
306 PR_vsnprintf(buf, sizeof(buf), fmt, ap);
307 va_end(ap);
308 fputs(q, stderr);
309 fputs(buf, stderr);
310 }
311 #endif /* SANITY */
312
313
314 /*
315 * Allocate a number of pages from the OS
316 */
317 static caddr_t
map_pages(int pages,int update)318 map_pages(int pages, int update)
319 {
320 caddr_t result,tail;
321
322 result = ((caddr_t)sbrk(0)) + malloc_pagemask - 1;
323 result = (caddr_t) ((u_long)result & ~malloc_pagemask);
324 tail = result + (pages << malloc_pageshift);
325 if (!brk(tail)) {
326 last_index = ((u_long)tail >> malloc_pageshift) - malloc_origo -1;
327 malloc_brk = tail;
328 TRACE(("%6d S %p .. %p\n",malloc_event++, result, tail));
329 if (!update || last_index < malloc_ninfo ||
330 extend_page_directory(last_index)) {
331 return result;
332 }
333 }
334 TRACE(("%6d s %d %p %d\n",malloc_event++,pages,sbrk(0),errno));
335 #ifdef EXTRA_SANITY
336 wrterror("map_pages fails\n");
337 #endif
338 return 0;
339 }
340
341 #define set_bit(_pi,_bit) \
342 (_pi)->bits[(_bit)/MALLOC_BITS] |= 1L<<((_bit)%MALLOC_BITS)
343
344 #define clr_bit(_pi,_bit) \
345 (_pi)->bits[(_bit)/MALLOC_BITS] &= ~(1L<<((_bit)%MALLOC_BITS));
346
347 #define tst_bit(_pi,_bit) \
348 ((_pi)->bits[(_bit)/MALLOC_BITS] & (1L<<((_bit)%MALLOC_BITS)))
349
350 /*
351 * Extend page directory
352 */
353 static int
extend_page_directory(u_long index)354 extend_page_directory(u_long index)
355 {
356 struct pginfo **young, **old;
357 int i;
358
359 TRACE(("%6d E %lu\n",malloc_event++,index));
360
361 /* Make it this many pages */
362 i = index * sizeof *page_dir;
363 i /= malloc_pagesize;
364 i += 2;
365
366 /* Get new pages, if you used this much mem you don't care :-) */
367 young = (struct pginfo**) map_pages(i,0);
368 if (!young) {
369 return 0;
370 }
371
372 /* Copy the old stuff */
373 memset(young, 0, i * malloc_pagesize);
374 memcpy(young, page_dir,
375 malloc_ninfo * sizeof *page_dir);
376
377 /* register the new size */
378 malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
379
380 /* swap the pointers */
381 old = page_dir;
382 page_dir = young;
383
384 /* Mark the pages */
385 index = ((u_long)young >> malloc_pageshift) - malloc_origo;
386 page_dir[index] = MALLOC_FIRST;
387 while (--i) {
388 page_dir[++index] = MALLOC_FOLLOW;
389 }
390
391 /* Now free the old stuff */
392 _PR_UnlockedFree(old);
393 return 1;
394 }
395
396 /*
397 * Set entry in page directory.
398 * Extend page directory if need be.
399 */
400 static int
set_pgdir(void * ptr,struct pginfo * info)401 set_pgdir(void *ptr, struct pginfo *info)
402 {
403 u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;
404
405 if (index >= malloc_ninfo && !extend_page_directory(index)) {
406 return 0;
407 }
408 page_dir[index] = info;
409 return 1;
410 }
411
412 /*
413 * Initialize the world
414 */
415 static void
malloc_init(void)416 malloc_init (void)
417 {
418 int i;
419 char *p;
420
421 TRACE(("%6d I\n",malloc_event++));
422 #ifdef DEBUG
423 for (p=getenv("MALLOC_OPTIONS"); p && *p; p++) {
424 switch (*p) {
425 case 'a': malloc_abort = 0; break;
426 case 'A': malloc_abort = 1; break;
427 case 'd': malloc_stats = 0; break;
428 case 'D': malloc_stats = 1; break;
429 case 'r': malloc_realloc = 0; break;
430 case 'R': malloc_realloc = 1; break;
431 default:
432 wrtwarning("Unknown chars in MALLOC_OPTIONS\n");
433 break;
434 }
435 }
436 #endif
437
438 #ifndef malloc_pagesize
439 /* determine our pagesize */
440 malloc_pagesize = getpagesize();
441 #endif /* malloc_pagesize */
442
443 #ifndef malloc_pageshift
444 /* determine how much we shift by to get there */
445 for (i = malloc_pagesize; i > 1; i >>= 1) {
446 malloc_pageshift++;
447 }
448 #endif /* malloc_pageshift */
449
450 #ifndef malloc_cache
451 malloc_cache = 50 << malloc_pageshift;
452 #endif /* malloc_cache */
453
454 #ifndef malloc_minsize
455 /*
456 * find the smallest size allocation we will bother about.
457 * this is determined as the smallest allocation that can hold
458 * it's own pginfo;
459 */
460 i = 2;
461 for(;;) {
462 int j;
463
464 /* Figure out the size of the bits */
465 j = malloc_pagesize/i;
466 j /= 8;
467 if (j < sizeof(u_long)) {
468 j = sizeof (u_long);
469 }
470 if (sizeof(struct pginfo) + j - sizeof (u_long) <= i) {
471 break;
472 }
473 i += i;
474 }
475 malloc_minsize = i;
476 #endif /* malloc_minsize */
477
478
479 /* Allocate one page for the page directory */
480 page_dir = (struct pginfo **) map_pages(1,0);
481 #ifdef SANITY
482 if (!page_dir) {
483 wrterror("fatal: my first mmap failed. (check limits ?)\n");
484 }
485 #endif
486
487 /*
488 * We need a maximum of malloc_pageshift buckets, steal these from the
489 * front of the page_directory;
490 */
491 malloc_origo = (u_long) page_dir >> malloc_pageshift;
492 malloc_origo -= malloc_pageshift;
493
494 /* Clear it */
495 memset(page_dir,0,malloc_pagesize);
496
497 /* Find out how much it tells us */
498 malloc_ninfo = malloc_pagesize / sizeof *page_dir;
499
500 /* Plug the page directory into itself */
501 i = set_pgdir(page_dir,MALLOC_FIRST);
502 #ifdef SANITY
503 if (!i) {
504 wrterror("fatal: couldn't set myself in the page directory\n");
505 }
506 #endif
507
508 /* Been here, done that */
509 initialized++;
510 }
511
512 /*
513 * Allocate a number of complete pages
514 */
malloc_pages(size_t size)515 static void *malloc_pages(size_t size)
516 {
517 void *p,*delay_free = 0;
518 int i;
519 struct pgfree *pf;
520 u_long index;
521
522 /* How many pages ? */
523 size += (malloc_pagesize-1);
524 size &= ~malloc_pagemask;
525
526 p = 0;
527 /* Look for free pages before asking for more */
528 for(pf = free_list.next; pf; pf = pf->next) {
529 #ifdef EXTRA_SANITY
530 if (pf->page == pf->end) {
531 wrterror("zero entry on free_list\n");
532 }
533 if (pf->page > pf->end) {
534 TRACE(("%6d !s %p %p %p <%d>\n",malloc_event++,
535 pf,pf->page,pf->end,__LINE__));
536 wrterror("sick entry on free_list\n");
537 }
538 if ((void*)pf->page >= (void*)sbrk(0)) {
539 wrterror("entry on free_list past brk\n");
540 }
541 if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo]
542 != MALLOC_FREE) {
543 TRACE(("%6d !f %p %p %p <%d>\n",malloc_event++,
544 pf,pf->page,pf->end,__LINE__));
545 wrterror("non-free first page on free-list\n");
546 }
547 if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo]
548 != MALLOC_FREE) {
549 wrterror("non-free last page on free-list\n");
550 }
551 #endif /* EXTRA_SANITY */
552 if (pf->size < size) {
553 continue;
554 }
555 else if (pf->size == size) {
556 p = pf->page;
557 if (pf->next) {
558 pf->next->prev = pf->prev;
559 }
560 pf->prev->next = pf->next;
561 delay_free = pf;
562 break;
563 } else {
564 p = pf->page;
565 pf->page += size;
566 pf->size -= size;
567 break;
568 }
569 }
570 #ifdef EXTRA_SANITY
571 if (p && page_dir[((u_long)p >> malloc_pageshift) - malloc_origo]
572 != MALLOC_FREE) {
573 wrterror("allocated non-free page on free-list\n");
574 }
575 #endif /* EXTRA_SANITY */
576
577 size >>= malloc_pageshift;
578
579 /* Map new pages */
580 if (!p) {
581 p = map_pages(size,1);
582 }
583
584 if (p) {
585 /* Mark the pages in the directory */
586 index = ((u_long)p >> malloc_pageshift) - malloc_origo;
587 page_dir[index] = MALLOC_FIRST;
588 for (i=1; i<size; i++) {
589 page_dir[index+i] = MALLOC_FOLLOW;
590 }
591 }
592 if (delay_free) {
593 if (!px) {
594 px = (struct pgfree*)delay_free;
595 }
596 else {
597 _PR_UnlockedFree(delay_free);
598 }
599 }
600 return p;
601 }
602
603 /*
604 * Allocate a page of fragments
605 */
606
607 static int
malloc_make_chunks(int bits)608 malloc_make_chunks(int bits)
609 {
610 struct pginfo *bp;
611 void *pp;
612 int i,k,l;
613
614 /* Allocate a new bucket */
615 pp = malloc_pages(malloc_pagesize);
616 if (!pp) {
617 return 0;
618 }
619 l = sizeof *bp - sizeof(u_long);
620 l += sizeof(u_long) *
621 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
622 if ((1<<(bits)) <= l+l) {
623 bp = (struct pginfo *)pp;
624 } else {
625 bp = (struct pginfo *)_PR_UnlockedMalloc(l);
626 }
627 if (!bp) {
628 return 0;
629 }
630 bp->size = (1<<bits);
631 bp->shift = bits;
632 bp->total = bp->free = malloc_pagesize >> bits;
633 bp->next = page_dir[bits];
634 bp->page = (char*)pp;
635 i = set_pgdir(pp,bp);
636 if (!i) {
637 return 0;
638 }
639
640 /* We can safely assume that there is nobody in this chain */
641 page_dir[bits] = bp;
642
643 /* set all valid bits in the bits */
644 k = bp->total;
645 i = 0;
646 /*
647 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
648 bp->bits[i / MALLOC_BITS] = ~0;
649 */
650 for(; i < k; i++) {
651 set_bit(bp,i);
652 }
653
654 if (bp != pp) {
655 return 1;
656 }
657
658 /* We may have used the first ones already */
659 for(i=0; l > 0; i++) {
660 clr_bit(bp,i);
661 bp->free--;
662 bp->total--;
663 l -= (1 << bits);
664 }
665 return 1;
666 }
667
668 /*
669 * Allocate a fragment
670 */
malloc_bytes(size_t size)671 static void *malloc_bytes(size_t size)
672 {
673 size_t s;
674 int j;
675 struct pginfo *bp;
676 int k;
677 u_long *lp, bf;
678
679 /* Don't bother with anything less than this */
680 if (size < malloc_minsize) {
681 size = malloc_minsize;
682 }
683
684 /* Find the right bucket */
685 j = 1;
686 s = size - 1;
687 while (s >>= 1) {
688 j++;
689 }
690
691 /* If it's empty, make a page more of that size chunks */
692 if (!page_dir[j] && !malloc_make_chunks(j)) {
693 return 0;
694 }
695
696 /* Find first word of bitmap which isn't empty */
697 bp = page_dir[j];
698 for (lp = bp->bits; !*lp; lp++)
699 ;
700
701 /* Find that bit */
702 bf = *lp;
703 k = 0;
704 while ((bf & 1) == 0) {
705 bf >>= 1;
706 k++;
707 }
708
709 *lp ^= 1L<<k; /* clear it */
710 bp->free--;
711 if (!bp->free) {
712 page_dir[j] = bp->next;
713 bp->next = 0;
714 }
715 k += (lp - bp->bits)*MALLOC_BITS;
716 return bp->page + (k << bp->shift);
717 }
718
_PR_UnlockedMalloc(size_t size)719 void *_PR_UnlockedMalloc(size_t size)
720 {
721 void *result;
722
723 /* Round up to a multiple of 8 bytes */
724 if (size & 7) {
725 size = size + 8 - (size & 7);
726 }
727
728 if (!initialized) {
729 malloc_init();
730 }
731
732 #ifdef SANITY
733 if (suicide) {
734 PR_Abort();
735 }
736 #endif
737
738 if (size <= malloc_maxsize) {
739 result = malloc_bytes(size);
740 }
741 else {
742 result = malloc_pages(size);
743 }
744 #ifdef SANITY
745 if (malloc_abort && !result) {
746 wrterror("malloc() returns NULL\n");
747 }
748 #endif
749 TRACE(("%6d M %p %d\n",malloc_event++,result,size));
750
751 return result;
752 }
753
_PR_UnlockedMemalign(size_t alignment,size_t size)754 void *_PR_UnlockedMemalign(size_t alignment, size_t size)
755 {
756 void *result;
757
758 /*
759 * alignment has to be a power of 2
760 */
761
762 if ((size <= alignment) && (alignment <= malloc_maxsize)) {
763 size = alignment;
764 }
765 else {
766 size += alignment - 1;
767 }
768
769 /* Round up to a multiple of 8 bytes */
770 if (size & 7) {
771 size = size + 8 - (size & 7);
772 }
773
774 if (!initialized) {
775 malloc_init();
776 }
777
778 #ifdef SANITY
779 if (suicide) {
780 abort();
781 }
782 #endif
783
784 if (size <= malloc_maxsize) {
785 result = malloc_bytes(size);
786 }
787 else {
788 result = malloc_pages(size);
789 }
790 #ifdef SANITY
791 if (malloc_abort && !result) {
792 wrterror("malloc() returns NULL\n");
793 }
794 #endif
795 TRACE(("%6d A %p %d\n",malloc_event++,result,size));
796
797 if ((u_long)result & (alignment - 1)) {
798 return ((void *)(((u_long)result + alignment) & ~(alignment - 1)));
799 }
800 else {
801 return result;
802 }
803 }
804
_PR_UnlockedCalloc(size_t n,size_t nelem)805 void *_PR_UnlockedCalloc(size_t n, size_t nelem)
806 {
807 void *p;
808
809 /* Compute total size and then round up to a double word amount */
810 n *= nelem;
811 if (n & 7) {
812 n = n + 8 - (n & 7);
813 }
814
815 /* Get the memory */
816 p = _PR_UnlockedMalloc(n);
817 if (p) {
818 /* Zero it */
819 memset(p, 0, n);
820 }
821 return p;
822 }
823
824 /*
825 * Change an allocation's size
826 */
_PR_UnlockedRealloc(void * ptr,size_t size)827 void *_PR_UnlockedRealloc(void *ptr, size_t size)
828 {
829 void *p;
830 u_long osize,page,index,tmp_index;
831 struct pginfo **mp;
832
833 if (!initialized) {
834 malloc_init();
835 }
836
837 #ifdef SANITY
838 if (suicide) {
839 PR_Abort();
840 }
841 #endif
842
843 /* used as free() */
844 TRACE(("%6d R %p %d\n",malloc_event++, ptr, size));
845 if (ptr && !size) {
846 _PR_UnlockedFree(ptr);
847 return _PR_UnlockedMalloc (1);
848 }
849
850 /* used as malloc() */
851 if (!ptr) {
852 p = _PR_UnlockedMalloc(size);
853 return p;
854 }
855
856 /* Find the page directory entry for the page in question */
857 page = (u_long)ptr >> malloc_pageshift;
858 index = page - malloc_origo;
859
860 /*
861 * check if memory was allocated by memalign
862 */
863 tmp_index = index;
864 while (page_dir[tmp_index] == MALLOC_FOLLOW) {
865 tmp_index--;
866 }
867 if (tmp_index != index) {
868 /*
869 * memalign-allocated memory
870 */
871 index = tmp_index;
872 page = index + malloc_origo;
873 ptr = (void *) (page << malloc_pageshift);
874 }
875 TRACE(("%6d R2 %p %d\n",malloc_event++, ptr, size));
876
877 /* make sure it makes sense in some fashion */
878 if (index < malloc_pageshift || index > last_index) {
879 #ifdef SANITY
880 wrtwarning("junk pointer passed to realloc()\n");
881 #endif
882 return 0;
883 }
884
885 /* find the size of that allocation, and see if we need to relocate */
886 mp = &page_dir[index];
887 if (*mp == MALLOC_FIRST) {
888 osize = malloc_pagesize;
889 while (mp[1] == MALLOC_FOLLOW) {
890 osize += malloc_pagesize;
891 mp++;
892 }
893 if (!malloc_realloc &&
894 size < osize &&
895 size > malloc_maxsize &&
896 size > (osize - malloc_pagesize)) {
897 return ptr;
898 }
899 } else if (*mp >= MALLOC_MAGIC) {
900 osize = (*mp)->size;
901 if (!malloc_realloc &&
902 size < osize &&
903 (size > (*mp)->size/2 || (*mp)->size == malloc_minsize)) {
904 return ptr;
905 }
906 } else {
907 #ifdef SANITY
908 wrterror("realloc() of wrong page.\n");
909 #endif
910 }
911
912 /* try to reallocate */
913 p = _PR_UnlockedMalloc(size);
914
915 if (p) {
916 /* copy the lesser of the two sizes */
917 if (osize < size) {
918 memcpy(p,ptr,osize);
919 }
920 else {
921 memcpy(p,ptr,size);
922 }
923 _PR_UnlockedFree(ptr);
924 }
925 #ifdef DEBUG
926 else if (malloc_abort) {
927 wrterror("realloc() returns NULL\n");
928 }
929 #endif
930
931 return p;
932 }
933
934 /*
935 * Free a sequence of pages
936 */
937
938 static void
free_pages(char * ptr,u_long page,int index,struct pginfo * info)939 free_pages(char *ptr, u_long page, int index, struct pginfo *info)
940 {
941 int i;
942 struct pgfree *pf,*pt;
943 u_long l;
944 char *tail;
945
946 TRACE(("%6d FP %p %d\n",malloc_event++, ptr, page));
947 /* Is it free already ? */
948 if (info == MALLOC_FREE) {
949 #ifdef SANITY
950 wrtwarning("freeing free page at %p.\n", ptr);
951 #endif
952 return;
953 }
954
955 #ifdef SANITY
956 /* Is it not the right place to begin ? */
957 if (info != MALLOC_FIRST) {
958 wrterror("freeing wrong page.\n");
959 }
960
961 /* Is this really a pointer to a page ? */
962 if ((u_long)ptr & malloc_pagemask) {
963 wrterror("freeing messed up page pointer.\n");
964 }
965 #endif
966
967 /* Count how many pages it is anyway */
968 page_dir[index] = MALLOC_FREE;
969 for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++) {
970 page_dir[index + i] = MALLOC_FREE;
971 }
972
973 l = i << malloc_pageshift;
974
975 tail = ptr+l;
976
977 /* add to free-list */
978 if (!px) {
979 px = (struct pgfree*)_PR_UnlockedMalloc(sizeof *pt);
980 }
981 /* XXX check success */
982 px->page = ptr;
983 px->end = tail;
984 px->size = l;
985 if (!free_list.next) {
986 px->next = free_list.next;
987 px->prev = &free_list;
988 free_list.next = px;
989 pf = px;
990 px = 0;
991 } else {
992 tail = ptr+l;
993 for(pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next)
994 ;
995 for(; pf; pf = pf->next) {
996 if (pf->end == ptr ) {
997 /* append to entry */
998 pf->end += l;
999 pf->size += l;
1000 if (pf->next && pf->end == pf->next->page ) {
1001 pt = pf->next;
1002 pf->end = pt->end;
1003 pf->size += pt->size;
1004 pf->next = pt->next;
1005 if (pf->next) {
1006 pf->next->prev = pf;
1007 }
1008 _PR_UnlockedFree(pt);
1009 }
1010 } else if (pf->page == tail) {
1011 /* prepend to entry */
1012 pf->size += l;
1013 pf->page = ptr;
1014 } else if (pf->page > ptr) {
1015 px->next = pf;
1016 px->prev = pf->prev;
1017 pf->prev = px;
1018 px->prev->next = px;
1019 pf = px;
1020 px = 0;
1021 } else if (!pf->next) {
1022 px->next = 0;
1023 px->prev = pf;
1024 pf->next = px;
1025 pf = px;
1026 px = 0;
1027 } else {
1028 continue;
1029 }
1030 break;
1031 }
1032 }
1033 if (!pf->next &&
1034 pf->size > malloc_cache &&
1035 pf->end == malloc_brk &&
1036 malloc_brk == (void*)sbrk(0)) {
1037 pf->end = pf->page + malloc_cache;
1038 pf->size = malloc_cache;
1039 TRACE(("%6d U %p %d\n",malloc_event++,pf->end,pf->end - pf->page));
1040 brk(pf->end);
1041 malloc_brk = pf->end;
1042 /* Find the page directory entry for the page in question */
1043 page = (u_long)pf->end >> malloc_pageshift;
1044 index = page - malloc_origo;
1045 /* Now update the directory */
1046 for(i=index; i <= last_index;) {
1047 page_dir[i++] = MALLOC_NOT_MINE;
1048 }
1049 last_index = index - 1;
1050 }
1051 }
1052
1053 /*
1054 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1055 */
1056
1057 static void
free_bytes(void * ptr,u_long page,int index,struct pginfo * info)1058 free_bytes(void *ptr, u_long page, int index, struct pginfo *info)
1059 {
1060 int i;
1061 struct pginfo **mp;
1062 void *vp;
1063
1064 /* Make sure that pointer is multiplum of chunk-size */
1065 #ifdef SANITY
1066 if ((u_long)ptr & (info->size - 1)) {
1067 wrterror("freeing messed up chunk pointer\n");
1068 }
1069 #endif
1070
1071 /* Find the chunk number on the page */
1072 i = ((u_long)ptr & malloc_pagemask) >> info->shift;
1073
1074 /* See if it's free already */
1075 if (tst_bit(info,i)) {
1076 #ifdef SANITY
1077 wrtwarning("freeing free chunk at %p\n", ptr);
1078 #endif
1079 return;
1080 }
1081
1082 /* Mark it free */
1083 set_bit(info,i);
1084 info->free++;
1085
1086 /* If the page was full before, we need to put it on the queue now */
1087 if (info->free == 1) {
1088 mp = page_dir + info->shift;
1089 while (*mp && (*mp)->next && (*mp)->next->page < info->page) {
1090 mp = &(*mp)->next;
1091 }
1092 info->next = *mp;
1093 *mp = info;
1094 return;
1095 }
1096
1097 /* If this page isn't empty, don't do anything. */
1098 if (info->free != info->total) {
1099 return;
1100 }
1101
1102 /* We may want to keep at least one page of each size chunks around. */
1103 mp = page_dir + info->shift;
1104 if (0 && (*mp == info) && !info->next) {
1105 return;
1106 }
1107
1108 /* Find & remove this page in the queue */
1109 while (*mp != info) {
1110 mp = &((*mp)->next);
1111 #ifdef EXTRA_SANITY
1112 if (!*mp) {
1113 TRACE(("%6d !q %p\n",malloc_event++,info));
1114 wrterror("Not on queue\n");
1115 }
1116 #endif
1117 }
1118 *mp = info->next;
1119
1120 /* Free the page & the info structure if need be */
1121 set_pgdir(info->page,MALLOC_FIRST);
1122 if((void*)info->page == (void*)info) {
1123 _PR_UnlockedFree(info->page);
1124 } else {
1125 vp = info->page;
1126 _PR_UnlockedFree(info);
1127 _PR_UnlockedFree(vp);
1128 }
1129 }
1130
_PR_UnlockedFree(void * ptr)1131 void _PR_UnlockedFree(void *ptr)
1132 {
1133 u_long page;
1134 struct pginfo *info;
1135 int index, tmp_index;
1136
1137 TRACE(("%6d F %p\n",malloc_event++,ptr));
1138 /* This is legal */
1139 if (!ptr) {
1140 return;
1141 }
1142
1143 #ifdef SANITY
1144 /* There wouldn't be anything to free */
1145 if (!initialized) {
1146 wrtwarning("free() called before malloc() ever got called\n");
1147 return;
1148 }
1149 #endif
1150
1151 #ifdef SANITY
1152 if (suicide) {
1153 PR_Abort();
1154 }
1155 #endif
1156
1157 /* Find the page directory entry for the page in question */
1158 page = (u_long)ptr >> malloc_pageshift;
1159 index = page - malloc_origo;
1160
1161 /*
1162 * check if memory was allocated by memalign
1163 */
1164 tmp_index = index;
1165 while (page_dir[tmp_index] == MALLOC_FOLLOW) {
1166 tmp_index--;
1167 }
1168 if (tmp_index != index) {
1169 /*
1170 * memalign-allocated memory
1171 */
1172 index = tmp_index;
1173 page = index + malloc_origo;
1174 ptr = (void *) (page << malloc_pageshift);
1175 }
1176 /* make sure it makes sense in some fashion */
1177 if (index < malloc_pageshift) {
1178 #ifdef SANITY
1179 wrtwarning("junk pointer %p (low) passed to free()\n", ptr);
1180 #endif
1181 return;
1182 }
1183 if (index > last_index) {
1184 #ifdef SANITY
1185 wrtwarning("junk pointer %p (high) passed to free()\n", ptr);
1186 #endif
1187 return;
1188 }
1189
1190 /* handle as page-allocation or chunk allocation */
1191 info = page_dir[index];
1192 if (info < MALLOC_MAGIC) {
1193 free_pages((char*)ptr, page, index, info);
1194 }
1195 else {
1196 free_bytes(ptr,page,index,info);
1197 }
1198 return;
1199 }
1200 #endif /* _PR_OVERRIDE_MALLOC */
1201