The Tor Browser / file comparison

comparison: nsprpub/pr/src/malloc/prmalloc.c

nsprpub/pr/src/malloc/prmalloc.c

changeset 1
ca08bd8f51b2
equal deleted inserted replaced
-1:000000000000 0:01bce1ec91b3
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
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
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
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
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 TRACE(("%6d s %d %p %d\n",malloc_event++,pages,sbrk(0),errno));
334 #ifdef EXTRA_SANITY
335 wrterror("map_pages fails\n");
336 #endif
337 return 0;
338 }
339
340 #define set_bit(_pi,_bit) \
341 (_pi)->bits[(_bit)/MALLOC_BITS] |= 1L<<((_bit)%MALLOC_BITS)
342
343 #define clr_bit(_pi,_bit) \
344 (_pi)->bits[(_bit)/MALLOC_BITS] &= ~(1L<<((_bit)%MALLOC_BITS));
345
346 #define tst_bit(_pi,_bit) \
347 ((_pi)->bits[(_bit)/MALLOC_BITS] & (1L<<((_bit)%MALLOC_BITS)))
348
349 /*
350 * Extend page directory
351 */
352 static int
353 extend_page_directory(u_long index)
354 {
355 struct pginfo **young, **old;
356 int i;
357
358 TRACE(("%6d E %lu\n",malloc_event++,index));
359
360 /* Make it this many pages */
361 i = index * sizeof *page_dir;
362 i /= malloc_pagesize;
363 i += 2;
364
365 /* Get new pages, if you used this much mem you don't care :-) */
366 young = (struct pginfo**) map_pages(i,0);
367 if (!young)
368 return 0;
369
370 /* Copy the old stuff */
371 memset(young, 0, i * malloc_pagesize);
372 memcpy(young, page_dir,
373 malloc_ninfo * sizeof *page_dir);
374
375 /* register the new size */
376 malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
377
378 /* swap the pointers */
379 old = page_dir;
380 page_dir = young;
381
382 /* Mark the pages */
383 index = ((u_long)young >> malloc_pageshift) - malloc_origo;
384 page_dir[index] = MALLOC_FIRST;
385 while (--i) {
386 page_dir[++index] = MALLOC_FOLLOW;
387 }
388
389 /* Now free the old stuff */
390 _PR_UnlockedFree(old);
391 return 1;
392 }
393
394 /*
395 * Set entry in page directory.
396 * Extend page directory if need be.
397 */
398 static int
399 set_pgdir(void *ptr, struct pginfo *info)
400 {
401 u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;
402
403 if (index >= malloc_ninfo && !extend_page_directory(index))
404 return 0;
405 page_dir[index] = info;
406 return 1;
407 }
408
409 /*
410 * Initialize the world
411 */
412 static void
413 malloc_init (void)
414 {
415 int i;
416 char *p;
417
418 TRACE(("%6d I\n",malloc_event++));
419 #ifdef DEBUG
420 for (p=getenv("MALLOC_OPTIONS"); p && *p; p++) {
421 switch (*p) {
422 case 'a': malloc_abort = 0; break;
423 case 'A': malloc_abort = 1; break;
424 case 'd': malloc_stats = 0; break;
425 case 'D': malloc_stats = 1; break;
426 case 'r': malloc_realloc = 0; break;
427 case 'R': malloc_realloc = 1; break;
428 default:
429 wrtwarning("Unknown chars in MALLOC_OPTIONS\n");
430 break;
431 }
432 }
433 #endif
434
435 #ifndef malloc_pagesize
436 /* determine our pagesize */
437 malloc_pagesize = getpagesize();
438 #endif /* malloc_pagesize */
439
440 #ifndef malloc_pageshift
441 /* determine how much we shift by to get there */
442 for (i = malloc_pagesize; i > 1; i >>= 1)
443 malloc_pageshift++;
444 #endif /* malloc_pageshift */
445
446 #ifndef malloc_cache
447 malloc_cache = 50 << malloc_pageshift;
448 #endif /* malloc_cache */
449
450 #ifndef malloc_minsize
451 /*
452 * find the smallest size allocation we will bother about.
453 * this is determined as the smallest allocation that can hold
454 * it's own pginfo;
455 */
456 i = 2;
457 for(;;) {
458 int j;
459
460 /* Figure out the size of the bits */
461 j = malloc_pagesize/i;
462 j /= 8;
463 if (j < sizeof(u_long))
464 j = sizeof (u_long);
465 if (sizeof(struct pginfo) + j - sizeof (u_long) <= i)
466 break;
467 i += i;
468 }
469 malloc_minsize = i;
470 #endif /* malloc_minsize */
471
472
473 /* Allocate one page for the page directory */
474 page_dir = (struct pginfo **) map_pages(1,0);
475 #ifdef SANITY
476 if (!page_dir)
477 wrterror("fatal: my first mmap failed. (check limits ?)\n");
478 #endif
479
480 /*
481 * We need a maximum of malloc_pageshift buckets, steal these from the
482 * front of the page_directory;
483 */
484 malloc_origo = (u_long) page_dir >> malloc_pageshift;
485 malloc_origo -= malloc_pageshift;
486
487 /* Clear it */
488 memset(page_dir,0,malloc_pagesize);
489
490 /* Find out how much it tells us */
491 malloc_ninfo = malloc_pagesize / sizeof *page_dir;
492
493 /* Plug the page directory into itself */
494 i = set_pgdir(page_dir,MALLOC_FIRST);
495 #ifdef SANITY
496 if (!i)
497 wrterror("fatal: couldn't set myself in the page directory\n");
498 #endif
499
500 /* Been here, done that */
501 initialized++;
502 }
503
504 /*
505 * Allocate a number of complete pages
506 */
507 static void *malloc_pages(size_t size)
508 {
509 void *p,*delay_free = 0;
510 int i;
511 struct pgfree *pf;
512 u_long index;
513
514 /* How many pages ? */
515 size += (malloc_pagesize-1);
516 size &= ~malloc_pagemask;
517
518 p = 0;
519 /* Look for free pages before asking for more */
520 for(pf = free_list.next; pf; pf = pf->next) {
521 #ifdef EXTRA_SANITY
522 if (pf->page == pf->end)
523 wrterror("zero entry on free_list\n");
524 if (pf->page > pf->end) {
525 TRACE(("%6d !s %p %p %p <%d>\n",malloc_event++,
526 pf,pf->page,pf->end,__LINE__));
527 wrterror("sick entry on free_list\n");
528 }
529 if ((void*)pf->page >= (void*)sbrk(0))
530 wrterror("entry on free_list past brk\n");
531 if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo]
532 != MALLOC_FREE) {
533 TRACE(("%6d !f %p %p %p <%d>\n",malloc_event++,
534 pf,pf->page,pf->end,__LINE__));
535 wrterror("non-free first page on free-list\n");
536 }
537 if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo]
538 != MALLOC_FREE)
539 wrterror("non-free last page on free-list\n");
540 #endif /* EXTRA_SANITY */
541 if (pf->size < size)
542 continue;
543 else if (pf->size == size) {
544 p = pf->page;
545 if (pf->next)
546 pf->next->prev = pf->prev;
547 pf->prev->next = pf->next;
548 delay_free = pf;
549 break;
550 } else {
551 p = pf->page;
552 pf->page += size;
553 pf->size -= size;
554 break;
555 }
556 }
557 #ifdef EXTRA_SANITY
558 if (p && page_dir[((u_long)p >> malloc_pageshift) - malloc_origo]
559 != MALLOC_FREE) {
560 wrterror("allocated non-free page on free-list\n");
561 }
562 #endif /* EXTRA_SANITY */
563
564 size >>= malloc_pageshift;
565
566 /* Map new pages */
567 if (!p)
568 p = map_pages(size,1);
569
570 if (p) {
571 /* Mark the pages in the directory */
572 index = ((u_long)p >> malloc_pageshift) - malloc_origo;
573 page_dir[index] = MALLOC_FIRST;
574 for (i=1;i<size;i++)
575 page_dir[index+i] = MALLOC_FOLLOW;
576 }
577 if (delay_free) {
578 if (!px)
579 px = (struct pgfree*)delay_free;
580 else
581 _PR_UnlockedFree(delay_free);
582 }
583 return p;
584 }
585
586 /*
587 * Allocate a page of fragments
588 */
589
590 static int
591 malloc_make_chunks(int bits)
592 {
593 struct pginfo *bp;
594 void *pp;
595 int i,k,l;
596
597 /* Allocate a new bucket */
598 pp = malloc_pages(malloc_pagesize);
599 if (!pp)
600 return 0;
601 l = sizeof *bp - sizeof(u_long);
602 l += sizeof(u_long) *
603 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
604 if ((1<<(bits)) <= l+l) {
605 bp = (struct pginfo *)pp;
606 } else {
607 bp = (struct pginfo *)_PR_UnlockedMalloc(l);
608 }
609 if (!bp)
610 return 0;
611 bp->size = (1<<bits);
612 bp->shift = bits;
613 bp->total = bp->free = malloc_pagesize >> bits;
614 bp->next = page_dir[bits];
615 bp->page = (char*)pp;
616 i = set_pgdir(pp,bp);
617 if (!i)
618 return 0;
619
620 /* We can safely assume that there is nobody in this chain */
621 page_dir[bits] = bp;
622
623 /* set all valid bits in the bits */
624 k = bp->total;
625 i = 0;
626 /*
627 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
628 bp->bits[i / MALLOC_BITS] = ~0;
629 */
630 for(; i < k; i++)
631 set_bit(bp,i);
632
633 if (bp != pp)
634 return 1;
635
636 /* We may have used the first ones already */
637 for(i=0;l > 0;i++) {
638 clr_bit(bp,i);
639 bp->free--;
640 bp->total--;
641 l -= (1 << bits);
642 }
643 return 1;
644 }
645
646 /*
647 * Allocate a fragment
648 */
649 static void *malloc_bytes(size_t size)
650 {
651 size_t s;
652 int j;
653 struct pginfo *bp;
654 int k;
655 u_long *lp, bf;
656
657 /* Don't bother with anything less than this */
658 if (size < malloc_minsize) {
659 size = malloc_minsize;
660 }
661
662 /* Find the right bucket */
663 j = 1;
664 s = size - 1;
665 while (s >>= 1) {
666 j++;
667 }
668
669 /* If it's empty, make a page more of that size chunks */
670 if (!page_dir[j] && !malloc_make_chunks(j))
671 return 0;
672
673 /* Find first word of bitmap which isn't empty */
674 bp = page_dir[j];
675 for (lp = bp->bits; !*lp; lp++)
676 ;
677
678 /* Find that bit */
679 bf = *lp;
680 k = 0;
681 while ((bf & 1) == 0) {
682 bf >>= 1;
683 k++;
684 }
685
686 *lp ^= 1L<<k; /* clear it */
687 bp->free--;
688 if (!bp->free) {
689 page_dir[j] = bp->next;
690 bp->next = 0;
691 }
692 k += (lp - bp->bits)*MALLOC_BITS;
693 return bp->page + (k << bp->shift);
694 }
695
696 void *_PR_UnlockedMalloc(size_t size)
697 {
698 void *result;
699
700 /* Round up to a multiple of 8 bytes */
701 if (size & 7) {
702 size = size + 8 - (size & 7);
703 }
704
705 if (!initialized)
706 malloc_init();
707
708 #ifdef SANITY
709 if (suicide)
710 PR_Abort();
711 #endif
712
713 if (size <= malloc_maxsize)
714 result = malloc_bytes(size);
715 else
716 result = malloc_pages(size);
717 #ifdef SANITY
718 if (malloc_abort && !result)
719 wrterror("malloc() returns NULL\n");
720 #endif
721 TRACE(("%6d M %p %d\n",malloc_event++,result,size));
722
723 return result;
724 }
725
726 void *_PR_UnlockedMemalign(size_t alignment, size_t size)
727 {
728 void *result;
729
730 /*
731 * alignment has to be a power of 2
732 */
733
734 if ((size <= alignment) && (alignment <= malloc_maxsize))
735 size = alignment;
736 else
737 size += alignment - 1;
738
739 /* Round up to a multiple of 8 bytes */
740 if (size & 7) {
741 size = size + 8 - (size & 7);
742 }
743
744 if (!initialized)
745 malloc_init();
746
747 #ifdef SANITY
748 if (suicide)
749 abort();
750 #endif
751
752 if (size <= malloc_maxsize)
753 result = malloc_bytes(size);
754 else
755 result = malloc_pages(size);
756 #ifdef SANITY
757 if (malloc_abort && !result)
758 wrterror("malloc() returns NULL\n");
759 #endif
760 TRACE(("%6d A %p %d\n",malloc_event++,result,size));
761
762 if ((u_long)result & (alignment - 1))
763 return ((void *)(((u_long)result + alignment) & ~(alignment - 1)));
764 else
765 return result;
766 }
767
768 void *_PR_UnlockedCalloc(size_t n, size_t nelem)
769 {
770 void *p;
771
772 /* Compute total size and then round up to a double word amount */
773 n *= nelem;
774 if (n & 7) {
775 n = n + 8 - (n & 7);
776 }
777
778 /* Get the memory */
779 p = _PR_UnlockedMalloc(n);
780 if (p) {
781 /* Zero it */
782 memset(p, 0, n);
783 }
784 return p;
785 }
786
787 /*
788 * Change an allocation's size
789 */
790 void *_PR_UnlockedRealloc(void *ptr, size_t size)
791 {
792 void *p;
793 u_long osize,page,index,tmp_index;
794 struct pginfo **mp;
795
796 if (!initialized)
797 malloc_init();
798
799 #ifdef SANITY
800 if (suicide)
801 PR_Abort();
802 #endif
803
804 /* used as free() */
805 TRACE(("%6d R %p %d\n",malloc_event++, ptr, size));
806 if (ptr && !size) {
807 _PR_UnlockedFree(ptr);
808 return _PR_UnlockedMalloc (1);
809 }
810
811 /* used as malloc() */
812 if (!ptr) {
813 p = _PR_UnlockedMalloc(size);
814 return p;
815 }
816
817 /* Find the page directory entry for the page in question */
818 page = (u_long)ptr >> malloc_pageshift;
819 index = page - malloc_origo;
820
821 /*
822 * check if memory was allocated by memalign
823 */
824 tmp_index = index;
825 while (page_dir[tmp_index] == MALLOC_FOLLOW)
826 tmp_index--;
827 if (tmp_index != index) {
828 /*
829 * memalign-allocated memory
830 */
831 index = tmp_index;
832 page = index + malloc_origo;
833 ptr = (void *) (page << malloc_pageshift);
834 }
835 TRACE(("%6d R2 %p %d\n",malloc_event++, ptr, size));
836
837 /* make sure it makes sense in some fashion */
838 if (index < malloc_pageshift || index > last_index) {
839 #ifdef SANITY
840 wrtwarning("junk pointer passed to realloc()\n");
841 #endif
842 return 0;
843 }
844
845 /* find the size of that allocation, and see if we need to relocate */
846 mp = &page_dir[index];
847 if (*mp == MALLOC_FIRST) {
848 osize = malloc_pagesize;
849 while (mp[1] == MALLOC_FOLLOW) {
850 osize += malloc_pagesize;
851 mp++;
852 }
853 if (!malloc_realloc &&
854 size < osize &&
855 size > malloc_maxsize &&
856 size > (osize - malloc_pagesize)) {
857 return ptr;
858 }
859 } else if (*mp >= MALLOC_MAGIC) {
860 osize = (*mp)->size;
861 if (!malloc_realloc &&
862 size < osize &&
863 (size > (*mp)->size/2 || (*mp)->size == malloc_minsize)) {
864 return ptr;
865 }
866 } else {
867 #ifdef SANITY
868 wrterror("realloc() of wrong page.\n");
869 #endif
870 }
871
872 /* try to reallocate */
873 p = _PR_UnlockedMalloc(size);
874
875 if (p) {
876 /* copy the lesser of the two sizes */
877 if (osize < size)
878 memcpy(p,ptr,osize);
879 else
880 memcpy(p,ptr,size);
881 _PR_UnlockedFree(ptr);
882 }
883 #ifdef DEBUG
884 else if (malloc_abort)
885 wrterror("realloc() returns NULL\n");
886 #endif
887
888 return p;
889 }
890
891 /*
892 * Free a sequence of pages
893 */
894
895 static void
896 free_pages(char *ptr, u_long page, int index, struct pginfo *info)
897 {
898 int i;
899 struct pgfree *pf,*pt;
900 u_long l;
901 char *tail;
902
903 TRACE(("%6d FP %p %d\n",malloc_event++, ptr, page));
904 /* Is it free already ? */
905 if (info == MALLOC_FREE) {
906 #ifdef SANITY
907 wrtwarning("freeing free page at %p.\n", ptr);
908 #endif
909 return;
910 }
911
912 #ifdef SANITY
913 /* Is it not the right place to begin ? */
914 if (info != MALLOC_FIRST)
915 wrterror("freeing wrong page.\n");
916
917 /* Is this really a pointer to a page ? */
918 if ((u_long)ptr & malloc_pagemask)
919 wrterror("freeing messed up page pointer.\n");
920 #endif
921
922 /* Count how many pages it is anyway */
923 page_dir[index] = MALLOC_FREE;
924 for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
925 page_dir[index + i] = MALLOC_FREE;
926
927 l = i << malloc_pageshift;
928
929 tail = ptr+l;
930
931 /* add to free-list */
932 if (!px)
933 px = (struct pgfree*)_PR_UnlockedMalloc(sizeof *pt);
934 /* XXX check success */
935 px->page = ptr;
936 px->end = tail;
937 px->size = l;
938 if (!free_list.next) {
939 px->next = free_list.next;
940 px->prev = &free_list;
941 free_list.next = px;
942 pf = px;
943 px = 0;
944 } else {
945 tail = ptr+l;
946 for(pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next)
947 ;
948 for(; pf; pf = pf->next) {
949 if (pf->end == ptr ) {
950 /* append to entry */
951 pf->end += l;
952 pf->size += l;
953 if (pf->next && pf->end == pf->next->page ) {
954 pt = pf->next;
955 pf->end = pt->end;
956 pf->size += pt->size;
957 pf->next = pt->next;
958 if (pf->next)
959 pf->next->prev = pf;
960 _PR_UnlockedFree(pt);
961 }
962 } else if (pf->page == tail) {
963 /* prepend to entry */
964 pf->size += l;
965 pf->page = ptr;
966 } else if (pf->page > ptr) {
967 px->next = pf;
968 px->prev = pf->prev;
969 pf->prev = px;
970 px->prev->next = px;
971 pf = px;
972 px = 0;
973 } else if (!pf->next) {
974 px->next = 0;
975 px->prev = pf;
976 pf->next = px;
977 pf = px;
978 px = 0;
979 } else {
980 continue;
981 }
982 break;
983 }
984 }
985 if (!pf->next &&
986 pf->size > malloc_cache &&
987 pf->end == malloc_brk &&
988 malloc_brk == (void*)sbrk(0)) {
989 pf->end = pf->page + malloc_cache;
990 pf->size = malloc_cache;
991 TRACE(("%6d U %p %d\n",malloc_event++,pf->end,pf->end - pf->page));
992 brk(pf->end);
993 malloc_brk = pf->end;
994 /* Find the page directory entry for the page in question */
995 page = (u_long)pf->end >> malloc_pageshift;
996 index = page - malloc_origo;
997 /* Now update the directory */
998 for(i=index;i <= last_index;)
999 page_dir[i++] = MALLOC_NOT_MINE;
1000 last_index = index - 1;
1001 }
1002 }
1003
1004 /*
1005 * Free a chunk, and possibly the page it's on, if the page becomes empty.
1006 */
1007
1008 static void
1009 free_bytes(void *ptr, u_long page, int index, struct pginfo *info)
1010 {
1011 int i;
1012 struct pginfo **mp;
1013 void *vp;
1014
1015 /* Make sure that pointer is multiplum of chunk-size */
1016 #ifdef SANITY
1017 if ((u_long)ptr & (info->size - 1))
1018 wrterror("freeing messed up chunk pointer\n");
1019 #endif
1020
1021 /* Find the chunk number on the page */
1022 i = ((u_long)ptr & malloc_pagemask) >> info->shift;
1023
1024 /* See if it's free already */
1025 if (tst_bit(info,i)) {
1026 #ifdef SANITY
1027 wrtwarning("freeing free chunk at %p\n", ptr);
1028 #endif
1029 return;
1030 }
1031
1032 /* Mark it free */
1033 set_bit(info,i);
1034 info->free++;
1035
1036 /* If the page was full before, we need to put it on the queue now */
1037 if (info->free == 1) {
1038 mp = page_dir + info->shift;
1039 while (*mp && (*mp)->next && (*mp)->next->page < info->page)
1040 mp = &(*mp)->next;
1041 info->next = *mp;
1042 *mp = info;
1043 return;
1044 }
1045
1046 /* If this page isn't empty, don't do anything. */
1047 if (info->free != info->total)
1048 return;
1049
1050 /* We may want to keep at least one page of each size chunks around. */
1051 mp = page_dir + info->shift;
1052 if (0 && (*mp == info) && !info->next)
1053 return;
1054
1055 /* Find & remove this page in the queue */
1056 while (*mp != info) {
1057 mp = &((*mp)->next);
1058 #ifdef EXTRA_SANITY
1059 if (!*mp) {
1060 TRACE(("%6d !q %p\n",malloc_event++,info));
1061 wrterror("Not on queue\n");
1062 }
1063 #endif
1064 }
1065 *mp = info->next;
1066
1067 /* Free the page & the info structure if need be */
1068 set_pgdir(info->page,MALLOC_FIRST);
1069 if((void*)info->page == (void*)info) {
1070 _PR_UnlockedFree(info->page);
1071 } else {
1072 vp = info->page;
1073 _PR_UnlockedFree(info);
1074 _PR_UnlockedFree(vp);
1075 }
1076 }
1077
1078 void _PR_UnlockedFree(void *ptr)
1079 {
1080 u_long page;
1081 struct pginfo *info;
1082 int index, tmp_index;
1083
1084 TRACE(("%6d F %p\n",malloc_event++,ptr));
1085 /* This is legal */
1086 if (!ptr)
1087 return;
1088
1089 #ifdef SANITY
1090 /* There wouldn't be anything to free */
1091 if (!initialized) {
1092 wrtwarning("free() called before malloc() ever got called\n");
1093 return;
1094 }
1095 #endif
1096
1097 #ifdef SANITY
1098 if (suicide)
1099 PR_Abort();
1100 #endif
1101
1102 /* Find the page directory entry for the page in question */
1103 page = (u_long)ptr >> malloc_pageshift;
1104 index = page - malloc_origo;
1105
1106 /*
1107 * check if memory was allocated by memalign
1108 */
1109 tmp_index = index;
1110 while (page_dir[tmp_index] == MALLOC_FOLLOW)
1111 tmp_index--;
1112 if (tmp_index != index) {
1113 /*
1114 * memalign-allocated memory
1115 */
1116 index = tmp_index;
1117 page = index + malloc_origo;
1118 ptr = (void *) (page << malloc_pageshift);
1119 }
1120 /* make sure it makes sense in some fashion */
1121 if (index < malloc_pageshift) {
1122 #ifdef SANITY
1123 wrtwarning("junk pointer %p (low) passed to free()\n", ptr);
1124 #endif
1125 return;
1126 }
1127 if (index > last_index) {
1128 #ifdef SANITY
1129 wrtwarning("junk pointer %p (high) passed to free()\n", ptr);
1130 #endif
1131 return;
1132 }
1133
1134 /* handle as page-allocation or chunk allocation */
1135 info = page_dir[index];
1136 if (info < MALLOC_MAGIC)
1137 free_pages((char*)ptr, page, index, info);
1138 else
1139 free_bytes(ptr,page,index,info);
1140 return;
1141 }
1142 #endif /* _PR_OVERRIDE_MALLOC */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial