开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 网络 > 查看源码
OpenBSD_malloc_Linux.c
资源名称：tor-0.2.1.20.tar.gz　[点击查看]
上传用户：awang829
上传日期：2019-07-14
资源大小：2356k
文件大小：45k
源码类别：

网络

开发平台：

Unix_Linux

OpenBSD_malloc_Linux.c：源码内容
  1. /* Version 1.83 for Linux.
  2.  * Compilation: gcc -shared -fPIC -O2 OpenBSD_malloc_Linux.c -o malloc.so
  3.  * Launching: LD_PRELOAD=/path/to/malloc.so firefox
  4.  */
  6. /* $OpenBSD: malloc.c,v 1.83 2006/05/14 19:53:40 otto Exp $ */
  8. /*
  9.  * ----------------------------------------------------------------------------
  10.  * "THE BEER-WARE LICENSE" (Revision 42):
  11.  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
  12.  * can do whatever you want with this stuff. If we meet some day, and you think
  13.  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
  14.  * ----------------------------------------------------------------------------
  15.  */
  17. /*
  18.  * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
  19.  * related to internal conditions and consistency in malloc.c. This has
  20.  * a noticeable runtime performance hit, and generally will not do you
  21.  * any good unless you fiddle with the internals of malloc or want
  22.  * to catch random pointer corruption as early as possible.
  23.  */
  24. #ifndef MALLOC_EXTRA_SANITY
  25. #undef MALLOC_EXTRA_SANITY
  26. #endif
  28. /*
  29.  * Defining MALLOC_STATS will enable you to call malloc_dump() and set
  30.  * the [dD] options in the MALLOC_OPTIONS environment variable.
  31.  * It has no run-time performance hit, but does pull in stdio...
  32.  */
  33. #ifndef MALLOC_STATS
  34. #undef MALLOC_STATS
  35. #endif
  37. /*
  38.  * What to use for Junk.  This is the byte value we use to fill with
  39.  * when the 'J' option is enabled.
  40.  */
  41. #define SOME_JUNK 0xd0 /* as in "Duh" :-) */
  43. #include <sys/types.h>
  44. #include <sys/time.h>
  45. #include <sys/resource.h>
  46. #include <sys/param.h>
  47. #include <sys/mman.h>
  48. #include <sys/uio.h>
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51. #include <string.h>
  52. #include <unistd.h>
  53. #include <fcntl.h>
  54. #include <limits.h>
  55. #include <errno.h>
  56. #include <err.h>
  57. /* For SIZE_T_MAX */
  58. #include "torint.h"
  60. //#include "thread_private.h"
  62. /*
  63.  * The basic parameters you can tweak.
  64.  *
  65.  * malloc_pageshift pagesize = 1 << malloc_pageshift
  66.  * It's probably best if this is the native
  67.  * page size, but it shouldn't have to be.
  68.  *
  69.  * malloc_minsize minimum size of an allocation in bytes.
  70.  * If this is too small it's too much work
  71.  * to manage them.  This is also the smallest
  72.  * unit of alignment used for the storage
  73.  * returned by malloc/realloc.
  74.  *
  75.  */
  77. static int align = 0;
  78. static size_t g_alignment = 0;
  80. extern int __libc_enable_secure;
  82. static int issetugid(void)
  83. {
  84. if (__libc_enable_secure) return 1;
  85. if (getuid() != geteuid()) return 1;
  86. if (getgid() != getegid()) return 1;
  87. return 0;
  88. }
  90. #define PGSHIFT 12
  91. #define MADV_FREE MADV_DONTNEED
  92. #include <pthread.h>
  93. static pthread_mutex_t gen_mutex = PTHREAD_MUTEX_INITIALIZER;
  95. #define _MALLOC_LOCK_INIT() {;}
  96. #define _MALLOC_LOCK() {pthread_mutex_lock(&gen_mutex);}
  97. #define _MALLOC_UNLOCK() {pthread_mutex_unlock(&gen_mutex);}
  99. #if defined(__sparc__) || defined(__alpha__)
  100. #define malloc_pageshift 13U
  101. #endif
  102. #if defined(__ia64__)
  103. #define malloc_pageshift 14U
  104. #endif
  106. #ifndef malloc_pageshift
  107. #define malloc_pageshift (PGSHIFT)
  108. #endif
  110. /*
  111.  * No user serviceable parts behind this point.
  112.  *
  113.  * This structure describes a page worth of chunks.
  114.  */
  115. struct pginfo {
  116. struct pginfo *next; /* next on the free list */
  117. void *page; /* Pointer to the page */
  118. u_short size; /* size of this page's chunks */
  119. u_short shift; /* How far to shift for this size chunks */
  120. u_short free; /* How many free chunks */
  121. u_short total; /* How many chunk */
  122. u_long bits[1];/* Which chunks are free */
  123. };
  125. /* How many bits per u_long in the bitmap */
  126. #define MALLOC_BITS (int)((NBBY * sizeof(u_long)))
  128. /*
  129.  * This structure describes a number of free pages.
  130.  */
  131. struct pgfree {
  132. struct pgfree *next; /* next run of free pages */
  133. struct pgfree *prev; /* prev run of free pages */
  134. void *page; /* pointer to free pages */
  135. void *pdir; /* pointer to the base page's dir */
  136. size_t size; /* number of bytes free */
  137. };
  139. /*
  140.  * Magic values to put in the page_directory
  141.  */
  142. #define MALLOC_NOT_MINE ((struct pginfo*) 0)
  143. #define MALLOC_FREE ((struct pginfo*) 1)
  144. #define MALLOC_FIRST ((struct pginfo*) 2)
  145. #define MALLOC_FOLLOW ((struct pginfo*) 3)
  146. #define MALLOC_MAGIC ((struct pginfo*) 4)
  148. #ifndef malloc_minsize
  149. #define malloc_minsize 16UL
  150. #endif
  152. #if !defined(malloc_pagesize)
  153. #define malloc_pagesize (1UL<<malloc_pageshift)
  154. #endif
  156. #if ((1UL<<malloc_pageshift) != malloc_pagesize)
  157. #error "(1UL<<malloc_pageshift) != malloc_pagesize"
  158. #endif
  160. #ifndef malloc_maxsize
  161. #define malloc_maxsize ((malloc_pagesize)>>1)
  162. #endif
  164. /* A mask for the offset inside a page. */
  165. #define malloc_pagemask ((malloc_pagesize)-1)
  167. #define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
  168. #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
  169. #define index2ptr(idx) ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift))
  171. /* Set when initialization has been done */
  172. static unsigned int malloc_started;
  174. /* Number of free pages we cache */
  175. static unsigned int malloc_cache = 16;
  177. /* Structure used for linking discrete directory pages. */
  178. struct pdinfo {
  179. struct pginfo **base;
  180. struct pdinfo *prev;
  181. struct pdinfo *next;
  182. u_long dirnum;
  183. };
  184. static struct pdinfo *last_dir; /* Caches to the last and previous */
  185. static struct pdinfo *prev_dir; /* referenced directory pages. */
  187. static size_t pdi_off;
  188. static u_long pdi_mod;
  189. #define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
  190. #define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
  191. #define PI_IDX(index) ((index) / pdi_mod)
  192. #define PI_OFF(index) ((index) % pdi_mod)
  194. /* The last index in the page directory we care about */
  195. static u_long last_index;
  197. /* Pointer to page directory. Allocated "as if with" malloc */
  198. static struct pginfo **page_dir;
  200. /* Free pages line up here */
  201. static struct pgfree free_list;
  203. /* Abort(), user doesn't handle problems. */
  204. static int malloc_abort = 2;
  206. /* Are we trying to die ? */
  207. static int suicide;
  209. #ifdef MALLOC_STATS
  210. /* dump statistics */
  211. static int malloc_stats;
  212. #endif
  214. /* avoid outputting warnings? */
  215. static int malloc_silent;
  217. /* always realloc ? */
  218. static int malloc_realloc;
  220. /* mprotect free pages PROT_NONE? */
  221. static int malloc_freeprot;
  223. /* use guard pages after allocations? */
  224. static size_t malloc_guard = 0;
  225. static size_t malloc_guarded;
  226. /* align pointers to end of page? */
  227. static int malloc_ptrguard;
  229. static int malloc_hint = 1;
  231. /* xmalloc behaviour ? */
  232. static int malloc_xmalloc;
  234. /* zero fill ? */
  235. static int malloc_zero;
  237. /* junk fill ? */
  238. static int malloc_junk;
  240. #ifdef __FreeBSD__
  241. /* utrace ? */
  242. static int malloc_utrace;
  244. struct ut {
  245. void *p;
  246. size_t s;
  247. void *r;
  248. };
  250. void utrace(struct ut *, int);
  252. #define UTRACE(a, b, c) 
  253. if (malloc_utrace) 
  254. {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
  255. #else /* !__FreeBSD__ */
  256. #define UTRACE(a,b,c)
  257. #endif
  259. /* Status of malloc. */
  260. static int malloc_active;
  262. /* Allocated memory. */
  263. static size_t malloc_used;
  265. /* My last break. */
  266. static caddr_t malloc_brk;
  268. /* One location cache for free-list holders. */
  269. static struct pgfree *px;
  271. /* Compile-time options. */
  272. char *malloc_options;
  274. /* Name of the current public function. */
  275. static const char *malloc_func;
  277. #define MMAP(size) 
  278. mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, 
  279.     -1, (off_t)0)
  281. /*
  282.  * Necessary function declarations.
  283.  */
  284. static void *imalloc(size_t size);
  285. static void ifree(void *ptr);
  286. static void *irealloc(void *ptr, size_t size);
  287. static void *malloc_bytes(size_t size);
  289. /*
  290.  * Function for page directory lookup.
  291.  */
  292. static int
  293. pdir_lookup(u_long index, struct pdinfo ** pdi)
  294. {
  295. struct pdinfo *spi;
  296. u_long pidx = PI_IDX(index);
  298. if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx)
  299. *pdi = last_dir;
  300. else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx)
  301. *pdi = prev_dir;
  302. else if (last_dir != NULL && prev_dir != NULL) {
  303. if ((PD_IDX(last_dir->dirnum) > pidx) ?
  304.     (PD_IDX(last_dir->dirnum) - pidx) :
  305.     (pidx - PD_IDX(last_dir->dirnum))
  306.     < (PD_IDX(prev_dir->dirnum) > pidx) ?
  307.     (PD_IDX(prev_dir->dirnum) - pidx) :
  308.     (pidx - PD_IDX(prev_dir->dirnum)))
  309. *pdi = last_dir;
  310. else
  311. *pdi = prev_dir;
  313. if (PD_IDX((*pdi)->dirnum) > pidx) {
  314. for (spi = (*pdi)->prev;
  315.     spi != NULL && PD_IDX(spi->dirnum) > pidx;
  316.     spi = spi->prev)
  317. *pdi = spi;
  318. if (spi != NULL)
  319. *pdi = spi;
  320. } else
  321. for (spi = (*pdi)->next;
  322.     spi != NULL && PD_IDX(spi->dirnum) <= pidx;
  323.     spi = spi->next)
  324. *pdi = spi;
  325. } else {
  326. *pdi = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
  327. for (spi = *pdi;
  328.     spi != NULL && PD_IDX(spi->dirnum) <= pidx;
  329.     spi = spi->next)
  330. *pdi = spi;
  331. }
  333. return ((PD_IDX((*pdi)->dirnum) == pidx) ? 0 :
  334.     (PD_IDX((*pdi)->dirnum) > pidx) ? 1 : -1);
  335. }
  337. #ifdef MALLOC_STATS
  338. void
  339. malloc_dump(int fd)
  340. {
  341. char buf[1024];
  342. struct pginfo **pd;
  343. struct pgfree *pf;
  344. struct pdinfo *pi;
  345. u_long j;
  347. pd = page_dir;
  348. pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
  350. /* print out all the pages */
  351. for (j = 0; j <= last_index;) {
  352. snprintf(buf, sizeof buf, "%08lx %5lu ", j << malloc_pageshift, j);
  353. write(fd, buf, strlen(buf));
  354. if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) {
  355. for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) {
  356. if (!PI_OFF(++j)) {
  357. if ((pi = pi->next) == NULL ||
  358.     PD_IDX(pi->dirnum) != PI_IDX(j))
  359. break;
  360. pd = pi->base;
  361. j += pdi_mod;
  362. }
  363. }
  364. j--;
  365. snprintf(buf, sizeof buf, ".. %5lu not minen", j);
  366. write(fd, buf, strlen(buf));
  367. } else if (pd[PI_OFF(j)] == MALLOC_FREE) {
  368. for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FREE;) {
  369. if (!PI_OFF(++j)) {
  370. if ((pi = pi->next) == NULL ||
  371.     PD_IDX(pi->dirnum) != PI_IDX(j))
  372. break;
  373. pd = pi->base;
  374. j += pdi_mod;
  375. }
  376. }
  377. j--;
  378. snprintf(buf, sizeof buf, ".. %5lu freen", j);
  379. write(fd, buf, strlen(buf));
  380. } else if (pd[PI_OFF(j)] == MALLOC_FIRST) {
  381. for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FOLLOW;) {
  382. if (!PI_OFF(++j)) {
  383. if ((pi = pi->next) == NULL ||
  384.     PD_IDX(pi->dirnum) != PI_IDX(j))
  385. break;
  386. pd = pi->base;
  387. j += pdi_mod;
  388. }
  389. }
  390. j--;
  391. snprintf(buf, sizeof buf, ".. %5lu in usen", j);
  392. write(fd, buf, strlen(buf));
  393. } else if (pd[PI_OFF(j)] < MALLOC_MAGIC) {
  394. snprintf(buf, sizeof buf, "(%p)n", pd[PI_OFF(j)]);
  395. write(fd, buf, strlen(buf));
  396. } else {
  397. snprintf(buf, sizeof buf, "%p %d (of %d) x %d @ %p --> %pn",
  398.     pd[PI_OFF(j)], pd[PI_OFF(j)]->free,
  399.     pd[PI_OFF(j)]->total, pd[PI_OFF(j)]->size,
  400.     pd[PI_OFF(j)]->page, pd[PI_OFF(j)]->next);
  401. write(fd, buf, strlen(buf));
  402. }
  403. if (!PI_OFF(++j)) {
  404. if ((pi = pi->next) == NULL)
  405. break;
  406. pd = pi->base;
  407. j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
  408. }
  409. }
  411. for (pf = free_list.next; pf; pf = pf->next) {
  412. snprintf(buf, sizeof buf, "Free: @%p [%p...%p[ %ld ->%p <-%pn",
  413.     pf, pf->page, (char *)pf->page + pf->size,
  414.     pf->size, pf->prev, pf->next);
  415. write(fd, buf, strlen(buf));
  416. if (pf == pf->next) {
  417. snprintf(buf, sizeof buf, "Free_list loopsn");
  418. write(fd, buf, strlen(buf));
  419. break;
  420. }
  421. }
  423. /* print out various info */
  424. snprintf(buf, sizeof buf, "Minsizet%lun", malloc_minsize);
  425. write(fd, buf, strlen(buf));
  426. snprintf(buf, sizeof buf, "Maxsizet%lun", malloc_maxsize);
  427. write(fd, buf, strlen(buf));
  428. snprintf(buf, sizeof buf, "Pagesizet%lun", malloc_pagesize);
  429. write(fd, buf, strlen(buf));
  430. snprintf(buf, sizeof buf, "Pageshiftt%un", malloc_pageshift);
  431. write(fd, buf, strlen(buf));
  432. snprintf(buf, sizeof buf, "In uset%lun", (u_long) malloc_used);
  433. write(fd, buf, strlen(buf));
  434. snprintf(buf, sizeof buf, "Guardedt%lun", (u_long) malloc_guarded);
  435. write(fd, buf, strlen(buf));
  436. }
  437. #endif /* MALLOC_STATS */
  439. extern char *__progname;
  441. static void
  442. wrterror(const char *p)
  443. {
  444. const char *q = " error: ";
  445. struct iovec iov[5];
  447. iov[0].iov_base = __progname;
  448. iov[0].iov_len = strlen(__progname);
  449. iov[1].iov_base = (char*)malloc_func;
  450. iov[1].iov_len = strlen(malloc_func);
  451. iov[2].iov_base = (char*)q;
  452. iov[2].iov_len = strlen(q);
  453. iov[3].iov_base = (char*)p;
  454. iov[3].iov_len = strlen(p);
  455. iov[4].iov_base = (char*)"n";
  456. iov[4].iov_len = 1;
  457. writev(STDERR_FILENO, iov, 5);
  459. suicide = 1;
  460. #ifdef MALLOC_STATS
  461. if (malloc_stats)
  462. malloc_dump(STDERR_FILENO);
  463. #endif /* MALLOC_STATS */
  464. malloc_active--;
  465. if (malloc_abort)
  466. abort();
  467. }
  469. static void
  470. wrtwarning(const char *p)
  471. {
  472. const char *q = " warning: ";
  473. struct iovec iov[5];
  475. if (malloc_abort)
  476. wrterror(p);
  477. else if (malloc_silent)
  478. return;
  480. iov[0].iov_base = __progname;
  481. iov[0].iov_len = strlen(__progname);
  482. iov[1].iov_base = (char*)malloc_func;
  483. iov[1].iov_len = strlen(malloc_func);
  484. iov[2].iov_base = (char*)q;
  485. iov[2].iov_len = strlen(q);
  486. iov[3].iov_base = (char*)p;
  487. iov[3].iov_len = strlen(p);
  488. iov[4].iov_base = (char*)"n";
  489. iov[4].iov_len = 1;
  491. writev(STDERR_FILENO, iov, 5);
  492. }
  494. #ifdef MALLOC_STATS
  495. static void
  496. malloc_exit(void)
  497. {
  498. char *q = "malloc() warning: Couldn't dump statsn";
  499. int save_errno = errno, fd;
  501. fd = open("malloc.out", O_RDWR|O_APPEND);
  502. if (fd != -1) {
  503. malloc_dump(fd);
  504. close(fd);
  505. } else
  506. write(STDERR_FILENO, q, strlen(q));
  507. errno = save_errno;
  508. }
  509. #endif /* MALLOC_STATS */
  511. /*
  512.  * Allocate aligned mmaped chunk
  513.  */
  515. static void *MMAP_A(size_t pages, size_t alignment)
  516. {
  517. void *j, *p;
  518. size_t first_size, rest, begin, end;
  519. if (pages%malloc_pagesize != 0)
  520. pages = pages - pages%malloc_pagesize + malloc_pagesize;
  521. first_size = pages + alignment - malloc_pagesize;
  522. p = MMAP(first_size);
  523. rest = ((size_t)p) % alignment;
  524. j = (rest == 0) ? p : (void*) ((size_t)p + alignment - rest);
  525. begin = (size_t)j - (size_t)p;
  526. if (begin != 0) munmap(p, begin);
  527. end = (size_t)p + first_size - ((size_t)j + pages);
  528. if(end != 0) munmap( (void*) ((size_t)j + pages), end);
  530. return j;
  531. }
  534. /*
  535.  * Allocate a number of pages from the OS
  536.  */
  537. static void *
  538. map_pages(size_t pages)
  539. {
  540. struct pdinfo *pi, *spi;
  541. struct pginfo **pd;
  542. u_long idx, pidx, lidx;
  543. caddr_t result, tail;
  544. u_long index, lindex;
  545. void  *pdregion = NULL;
  546. size_t dirs, cnt;
  548. pages <<= malloc_pageshift;
  549. if (!align)
  550. result = MMAP(pages + malloc_guard);
  551. else {
  552. result = MMAP_A(pages + malloc_guard, g_alignment);
  553. }
  554. if (result == MAP_FAILED) {
  555. #ifdef MALLOC_EXTRA_SANITY
  556. wrtwarning("(ES): map_pages fails");
  557. #endif /* MALLOC_EXTRA_SANITY */
  558. errno = ENOMEM;
  559. return (NULL);
  560. }
  561. index = ptr2index(result);
  562. tail = result + pages + malloc_guard;
  563. lindex = ptr2index(tail) - 1;
  564. if (malloc_guard)
  565. mprotect(result + pages, malloc_guard, PROT_NONE);
  567. pidx = PI_IDX(index);
  568. lidx = PI_IDX(lindex);
  570. if (tail > malloc_brk) {
  571. malloc_brk = tail;
  572. last_index = lindex;
  573. }
  575. dirs = lidx - pidx;
  577. /* Insert directory pages, if needed. */
  578. if (pdir_lookup(index, &pi) != 0)
  579. dirs++;
  581. if (dirs > 0) {
  582. pdregion = MMAP(malloc_pagesize * dirs);
  583. if (pdregion == MAP_FAILED) {
  584. munmap(result, tail - result);
  585. #ifdef MALLOC_EXTRA_SANITY
  586. wrtwarning("(ES): map_pages fails");
  587. #endif
  588. errno = ENOMEM;
  589. return (NULL);
  590. }
  591. }
  593. cnt = 0;
  594. for (idx = pidx, spi = pi; idx <= lidx; idx++) {
  595. if (pi == NULL || PD_IDX(pi->dirnum) != idx) {
  596. pd = (struct pginfo **)((char *)pdregion +
  597.     cnt * malloc_pagesize);
  598. cnt++;
  599. memset(pd, 0, malloc_pagesize);
  600. pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
  601. pi->base = pd;
  602. pi->prev = spi;
  603. pi->next = spi->next;
  604. pi->dirnum = idx * (malloc_pagesize /
  605.     sizeof(struct pginfo *));
  607. if (spi->next != NULL)
  608. spi->next->prev = pi;
  609. spi->next = pi;
  610. }
  611. if (idx > pidx && idx < lidx) {
  612. pi->dirnum += pdi_mod;
  613. } else if (idx == pidx) {
  614. if (pidx == lidx) {
  615. pi->dirnum += (u_long)(tail - result) >>
  616.     malloc_pageshift;
  617. } else {
  618. pi->dirnum += pdi_mod - PI_OFF(index);
  619. }
  620. } else {
  621. pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
  622. }
  623. #ifdef MALLOC_EXTRA_SANITY
  624. if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > idx) {
  625. wrterror("(ES): pages directory overflow");
  626. errno = EFAULT;
  627. return (NULL);
  628. }
  629. #endif /* MALLOC_EXTRA_SANITY */
  630. if (idx == pidx && pi != last_dir) {
  631. prev_dir = last_dir;
  632. last_dir = pi;
  633. }
  634. spi = pi;
  635. pi = spi->next;
  636. }
  637. #ifdef MALLOC_EXTRA_SANITY
  638. if (cnt > dirs)
  639. wrtwarning("(ES): cnt > dirs");
  640. #endif /* MALLOC_EXTRA_SANITY */
  641. if (cnt < dirs)
  642. munmap((char *)pdregion + cnt * malloc_pagesize,
  643.     (dirs - cnt) * malloc_pagesize);
  645. return (result);
  646. }
  648. /*
  649.  * Initialize the world
  650.  */
  651. static void
  652. malloc_init(void)
  653. {
  654. char *p, b[64];
  655. int i, j, save_errno = errno;
  657. _MALLOC_LOCK_INIT();
  659. #ifdef MALLOC_EXTRA_SANITY
  660. malloc_junk = 1;
  661. #endif /* MALLOC_EXTRA_SANITY */
  663. for (i = 0; i < 3; i++) {
  664. switch (i) {
  665. case 0:
  666. j = readlink("/etc/malloc.conf", b, sizeof b - 1);
  667. if (j <= 0)
  668. continue;
  669. b[j] = '';
  670. p = b;
  671. break;
  672. case 1:
  673. if (issetugid() == 0)
  674. p = getenv("MALLOC_OPTIONS");
  675. else
  676. continue;
  677. break;
  678. case 2:
  679. p = malloc_options;
  680. break;
  681. default:
  682. p = NULL;
  683. }
  685. for (; p != NULL && *p != ''; p++) {
  686. switch (*p) {
  687. case '>':
  688. malloc_cache <<= 1;
  689. break;
  690. case '<':
  691. malloc_cache >>= 1;
  692. break;
  693. case 'a':
  694. malloc_abort = 0;
  695. break;
  696. case 'A':
  697. malloc_abort = 1;
  698. break;
  699. #ifdef MALLOC_STATS
  700. case 'd':
  701. malloc_stats = 0;
  702. break;
  703. case 'D':
  704. malloc_stats = 1;
  705. break;
  706. #endif /* MALLOC_STATS */
  707. case 'f':
  708. malloc_freeprot = 0;
  709. break;
  710. case 'F':
  711. malloc_freeprot = 1;
  712. break;
  713. case 'g':
  714. malloc_guard = 0;
  715. break;
  716. case 'G':
  717. malloc_guard = malloc_pagesize;
  718. break;
  719. case 'h':
  720. malloc_hint = 0;
  721. break;
  722. case 'H':
  723. malloc_hint = 1;
  724. break;
  725. case 'j':
  726. malloc_junk = 0;
  727. break;
  728. case 'J':
  729. malloc_junk = 1;
  730. break;
  731. case 'n':
  732. malloc_silent = 0;
  733. break;
  734. case 'N':
  735. malloc_silent = 1;
  736. break;
  737. case 'p':
  738. malloc_ptrguard = 0;
  739. break;
  740. case 'P':
  741. malloc_ptrguard = 1;
  742. break;
  743. case 'r':
  744. malloc_realloc = 0;
  745. break;
  746. case 'R':
  747. malloc_realloc = 1;
  748. break;
  749. #ifdef __FreeBSD__
  750. case 'u':
  751. malloc_utrace = 0;
  752. break;
  753. case 'U':
  754. malloc_utrace = 1;
  755. break;
  756. #endif /* __FreeBSD__ */
  757. case 'x':
  758. malloc_xmalloc = 0;
  759. break;
  760. case 'X':
  761. malloc_xmalloc = 1;
  762. break;
  763. case 'z':
  764. malloc_zero = 0;
  765. break;
  766. case 'Z':
  767. malloc_zero = 1;
  768. break;
  769. default:
  770. j = malloc_abort;
  771. malloc_abort = 0;
  772. wrtwarning("unknown char in MALLOC_OPTIONS");
  773. malloc_abort = j;
  774. break;
  775. }
  776. }
  777. }
  779. UTRACE(0, 0, 0);
  781. /*
  782.  * We want junk in the entire allocation, and zero only in the part
  783.  * the user asked for.
  784.  */
  785. if (malloc_zero)
  786. malloc_junk = 1;
  788. #ifdef MALLOC_STATS
  789. if (malloc_stats && (atexit(malloc_exit) == -1))
  790. wrtwarning("atexit(2) failed."
  791.     "  Will not be able to dump malloc stats on exit");
  792. #endif /* MALLOC_STATS */
  794. if (malloc_pagesize != getpagesize()) {
  795. wrterror("malloc() replacement compiled with a different "
  796.  "page size from what we're running with.  Failing.");
  797. errno = ENOMEM;
  798. return;
  799. }
  801. /* Allocate one page for the page directory. */
  802. page_dir = (struct pginfo **)MMAP(malloc_pagesize);
  804. if (page_dir == MAP_FAILED) {
  805. wrterror("mmap(2) failed, check limits");
  806. errno = ENOMEM;
  807. return;
  808. }
  809. pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
  810. pdi_mod = pdi_off / sizeof(struct pginfo *);
  812. last_dir = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
  813. last_dir->base = page_dir;
  814. last_dir->prev = last_dir->next = NULL;
  815. last_dir->dirnum = malloc_pageshift;
  817. /* Been here, done that. */
  818. malloc_started++;
  820. /* Recalculate the cache size in bytes, and make sure it's nonzero. */
  821. if (!malloc_cache)
  822. malloc_cache++;
  823. malloc_cache <<= malloc_pageshift;
  824. errno = save_errno;
  825. }
  827. /*
  828.  * Allocate a number of complete pages
  829.  */
  830. static void *
  831. malloc_pages(size_t size)
  832. {
  833. void *p, *delay_free = NULL, *tp;
  834. size_t i;
  835. struct pginfo **pd;
  836. struct pdinfo *pi;
  837. u_long pidx, index;
  838. struct pgfree *pf;
  840. size = pageround(size) + malloc_guard;
  842. p = NULL;
  843. /* Look for free pages before asking for more */
  844. if (!align)
  845. for (pf = free_list.next; pf; pf = pf->next) {
  847. #ifdef MALLOC_EXTRA_SANITY
  848. if (pf->size & malloc_pagemask) {
  849. wrterror("(ES): junk length entry on free_list");
  850. errno = EFAULT;
  851. return (NULL);
  852. }
  853. if (!pf->size) {
  854. wrterror("(ES): zero length entry on free_list");
  855. errno = EFAULT;
  856. return (NULL);
  857. }
  858. if (pf->page > (pf->page + pf->size)) {
  859. wrterror("(ES): sick entry on free_list");
  860. errno = EFAULT;
  861. return (NULL);
  862. }
  863. if ((pi = pf->pdir) == NULL) {
  864. wrterror("(ES): invalid page directory on free-list");
  865. errno = EFAULT;
  866. return (NULL);
  867. }
  868. if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
  869. wrterror("(ES): directory index mismatch on free-list");
  870. errno = EFAULT;
  871. return (NULL);
  872. }
  873. pd = pi->base;
  874. if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
  875. wrterror("(ES): non-free first page on free-list");
  876. errno = EFAULT;
  877. return (NULL);
  878. }
  879. pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1);
  880. for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
  881.     pi = pi->next)
  882. ;
  883. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  884. wrterror("(ES): last page not referenced in page directory");
  885. errno = EFAULT;
  886. return (NULL);
  887. }
  888. pd = pi->base;
  889. if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) {
  890. wrterror("(ES): non-free last page on free-list");
  891. errno = EFAULT;
  892. return (NULL);
  893. }
  894. #endif /* MALLOC_EXTRA_SANITY */
  896. if (pf->size < size)
  897. continue;
  899. if (pf->size == size) {
  900. p = pf->page;
  901. pi = pf->pdir;
  902. if (pf->next != NULL)
  903. pf->next->prev = pf->prev;
  904. pf->prev->next = pf->next;
  905. delay_free = pf;
  906. break;
  907. }
  908. p = pf->page;
  909. pf->page = (char *) pf->page + size;
  910. pf->size -= size;
  911. pidx = PI_IDX(ptr2index(pf->page));
  912. for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
  913.     pi = pi->next)
  914. ;
  915. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  916. wrterror("(ES): hole in directories");
  917. errno = EFAULT;
  918. return (NULL);
  919. }
  920. tp = pf->pdir;
  921. pf->pdir = pi;
  922. pi = tp;
  923. break;
  924. }
  926. size -= malloc_guard;
  928. #ifdef MALLOC_EXTRA_SANITY
  929. if (p != NULL && pi != NULL) {
  930. pidx = PD_IDX(pi->dirnum);
  931. pd = pi->base;
  932. }
  933. if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
  934. wrterror("(ES): allocated non-free page on free-list");
  935. errno = EFAULT;
  936. return (NULL);
  937. }
  938. #endif /* MALLOC_EXTRA_SANITY */
  940. if (p != NULL && (malloc_guard || malloc_freeprot))
  941. mprotect(p, size, PROT_READ | PROT_WRITE);
  943. size >>= malloc_pageshift;
  945. /* Map new pages */
  946. if (p == NULL)
  947. p = map_pages(size);
  949. if (p != NULL) {
  950. index = ptr2index(p);
  951. pidx = PI_IDX(index);
  952. pdir_lookup(index, &pi);
  953. #ifdef MALLOC_EXTRA_SANITY
  954. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  955. wrterror("(ES): mapped pages not found in directory");
  956. errno = EFAULT;
  957. return (NULL);
  958. }
  959. #endif /* MALLOC_EXTRA_SANITY */
  960. if (pi != last_dir) {
  961. prev_dir = last_dir;
  962. last_dir = pi;
  963. }
  964. pd = pi->base;
  965. pd[PI_OFF(index)] = MALLOC_FIRST;
  967. for (i = 1; i < size; i++) {
  968. if (!PI_OFF(index + i)) {
  969. pidx++;
  970. pi = pi->next;
  971. #ifdef MALLOC_EXTRA_SANITY
  972. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  973. wrterror("(ES): hole in mapped pages directory");
  974. errno = EFAULT;
  975. return (NULL);
  976. }
  977. #endif /* MALLOC_EXTRA_SANITY */
  978. pd = pi->base;
  979. }
  980. pd[PI_OFF(index + i)] = MALLOC_FOLLOW;
  981. }
  982. if (malloc_guard) {
  983. if (!PI_OFF(index + i)) {
  984. pidx++;
  985. pi = pi->next;
  986. #ifdef MALLOC_EXTRA_SANITY
  987. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  988. wrterror("(ES): hole in mapped pages directory");
  989. errno = EFAULT;
  990. return (NULL);
  991. }
  992. #endif /* MALLOC_EXTRA_SANITY */
  993. pd = pi->base;
  994. }
  995. pd[PI_OFF(index + i)] = MALLOC_FIRST;
  996. }
  998. malloc_used += size << malloc_pageshift;
  999. malloc_guarded += malloc_guard;
  1001. if (malloc_junk)
  1002. memset(p, SOME_JUNK, size << malloc_pageshift);
  1003. }
  1004. if (delay_free) {
  1005. if (px == NULL)
  1006. px = delay_free;
  1007. else
  1008. ifree(delay_free);
  1009. }
  1010. return (p);
  1011. }
  1013. /*
  1014.  * Allocate a page of fragments
  1015.  */
  1017. static __inline__ int
  1018. malloc_make_chunks(int bits)
  1019. {
  1020. struct pginfo *bp, **pd;
  1021. struct pdinfo *pi;
  1022. #ifdef MALLOC_EXTRA_SANITY
  1023. u_long pidx;
  1024. #endif /* MALLOC_EXTRA_SANITY */
  1025. void *pp;
  1026. long i, k;
  1027. size_t l;
  1029. /* Allocate a new bucket */
  1030. pp = malloc_pages((size_t) malloc_pagesize);
  1031. if (pp == NULL)
  1032. return (0);
  1034. /* Find length of admin structure */
  1035. l = sizeof *bp - sizeof(u_long);
  1036. l += sizeof(u_long) *
  1037.     (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);
  1039. /* Don't waste more than two chunks on this */
  1041. /*
  1042.  * If we are to allocate a memory protected page for the malloc(0)
  1043.  * case (when bits=0), it must be from a different page than the
  1044.  * pginfo page.
  1045.  * --> Treat it like the big chunk alloc, get a second data page.
  1046.  */
  1047. if (bits != 0 && (1UL << (bits)) <= l + l) {
  1048. bp = (struct pginfo *) pp;
  1049. } else {
  1050. bp = (struct pginfo *) imalloc(l);
  1051. if (bp == NULL) {
  1052. ifree(pp);
  1053. return (0);
  1054. }
  1055. }
  1057. /* memory protect the page allocated in the malloc(0) case */
  1058. if (bits == 0) {
  1059. bp->size = 0;
  1060. bp->shift = 1;
  1061. i = malloc_minsize - 1;
  1062. while (i >>= 1)
  1063. bp->shift++;
  1064. bp->total = bp->free = malloc_pagesize >> bp->shift;
  1065. bp->page = pp;
  1067. k = mprotect(pp, malloc_pagesize, PROT_NONE);
  1068. if (k < 0) {
  1069. ifree(pp);
  1070. ifree(bp);
  1071. return (0);
  1072. }
  1073. } else {
  1074. bp->size = (1UL << bits);
  1075. bp->shift = bits;
  1076. bp->total = bp->free = malloc_pagesize >> bits;
  1077. bp->page = pp;
  1078. }
  1080. /* set all valid bits in the bitmap */
  1081. k = bp->total;
  1082. i = 0;
  1084. /* Do a bunch at a time */
  1085. for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
  1086. bp->bits[i / MALLOC_BITS] = ~0UL;
  1088. for (; i < k; i++)
  1089. bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
  1091. k = (long)l;
  1092. if (bp == bp->page) {
  1093. /* Mark the ones we stole for ourselves */
  1094. for (i = 0; k > 0; i++) {
  1095. bp->bits[i / MALLOC_BITS] &= ~(1UL << (i % MALLOC_BITS));
  1096. bp->free--;
  1097. bp->total--;
  1098. k -= (1 << bits);
  1099. }
  1100. }
  1101. /* MALLOC_LOCK */
  1103. pdir_lookup(ptr2index(pp), &pi);
  1104. #ifdef MALLOC_EXTRA_SANITY
  1105. pidx = PI_IDX(ptr2index(pp));
  1106. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  1107. wrterror("(ES): mapped pages not found in directory");
  1108. errno = EFAULT;
  1109. return (0);
  1110. }
  1111. #endif /* MALLOC_EXTRA_SANITY */
  1112. if (pi != last_dir) {
  1113. prev_dir = last_dir;
  1114. last_dir = pi;
  1115. }
  1116. pd = pi->base;
  1117. pd[PI_OFF(ptr2index(pp))] = bp;
  1119. bp->next = page_dir[bits];
  1120. page_dir[bits] = bp;
  1122. /* MALLOC_UNLOCK */
  1123. return (1);
  1124. }
  1126. /*
  1127.  * Allocate a fragment
  1128.  */
  1129. static void *
  1130. malloc_bytes(size_t size)
  1131. {
  1132. int i, j;
  1133. size_t k;
  1134. u_long u, *lp;
  1135. struct pginfo *bp;
  1137. /* Don't bother with anything less than this */
  1138. /* unless we have a malloc(0) requests */
  1139. if (size != 0 && size < malloc_minsize)
  1140. size = malloc_minsize;
  1142. /* Find the right bucket */
  1143. if (size == 0)
  1144. j = 0;
  1145. else {
  1146. j = 1;
  1147. i = size - 1;
  1148. while (i >>= 1)
  1149. j++;
  1150. }
  1152. /* If it's empty, make a page more of that size chunks */
  1153. if (page_dir[j] == NULL && !malloc_make_chunks(j))
  1154. return (NULL);
  1156. bp = page_dir[j];
  1158. /* Find first word of bitmap which isn't empty */
  1159. for (lp = bp->bits; !*lp; lp++);
  1161. /* Find that bit, and tweak it */
  1162. u = 1;
  1163. k = 0;
  1164. while (!(*lp & u)) {
  1165. u += u;
  1166. k++;
  1167. }
  1169. if (malloc_guard) {
  1170. /* Walk to a random position. */
  1171. // i = arc4random() % bp->free;
  1172. i = rand() % bp->free;
  1173. while (i > 0) {
  1174. u += u;
  1175. k++;
  1176. if (k >= MALLOC_BITS) {
  1177. lp++;
  1178. u = 1;
  1179. k = 0;
  1180. }
  1181. #ifdef MALLOC_EXTRA_SANITY
  1182. if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
  1183. wrterror("chunk overflow");
  1184. errno = EFAULT;
  1185. return (NULL);
  1186. }
  1187. #endif /* MALLOC_EXTRA_SANITY */
  1188. if (*lp & u)
  1189. i--;
  1190. }
  1191. }
  1192. *lp ^= u;
  1194. /* If there are no more free, remove from free-list */
  1195. if (!--bp->free) {
  1196. page_dir[j] = bp->next;
  1197. bp->next = NULL;
  1198. }
  1199. /* Adjust to the real offset of that chunk */
  1200. k += (lp - bp->bits) * MALLOC_BITS;
  1201. k <<= bp->shift;
  1203. if (malloc_junk && bp->size != 0)
  1204. memset((char *)bp->page + k, SOME_JUNK, (size_t)bp->size);
  1206. return ((u_char *) bp->page + k);
  1207. }
  1209. /*
  1210.  * Magic so that malloc(sizeof(ptr)) is near the end of the page.
  1211.  */
  1212. #define PTR_GAP (malloc_pagesize - sizeof(void *))
  1213. #define PTR_SIZE (sizeof(void *))
  1214. #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP)
  1216. /*
  1217.  * Allocate a piece of memory
  1218.  */
  1219. static void *
  1220. imalloc(size_t size)
  1221. {
  1222. void *result;
  1223. int ptralloc = 0;
  1225. if (!malloc_started)
  1226. malloc_init();
  1228. if (suicide)
  1229. abort();
  1231. /* does not matter if malloc_bytes fails */
  1232. if (px == NULL)
  1233. px = malloc_bytes(sizeof *px);
  1235. if (malloc_ptrguard && size == PTR_SIZE) {
  1236. ptralloc = 1;
  1237. size = malloc_pagesize;
  1238. }
  1239. if ((size + malloc_pagesize) < size) { /* Check for overflow */
  1240. result = NULL;
  1241. errno = ENOMEM;
  1242. } else if (size <= malloc_maxsize)
  1243. result = malloc_bytes(size);
  1244. else
  1245. result = malloc_pages(size);
  1247. if (malloc_abort == 1 && result == NULL)
  1248. wrterror("allocation failed");
  1250. if (malloc_zero && result != NULL)
  1251. memset(result, 0, size);
  1253. if (result && ptralloc)
  1254. return ((char *) result + PTR_GAP);
  1255. return (result);
  1256. }
  1258. /*
  1259.  * Change the size of an allocation.
  1260.  */
  1261. static void *
  1262. irealloc(void *ptr, size_t size)
  1263. {
  1264. void *p;
  1265. size_t osize;
  1266. u_long index, i;
  1267. struct pginfo **mp;
  1268. struct pginfo **pd;
  1269. struct pdinfo *pi;
  1270. #ifdef MALLOC_EXTRA_SANITY
  1271. u_long pidx;
  1272. #endif /* MALLOC_EXTRA_SANITY */
  1274. if (suicide)
  1275. abort();
  1277. if (!malloc_started) {
  1278. wrtwarning("malloc() has never been called");
  1279. return (NULL);
  1280. }
  1281. if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
  1282. if (size <= PTR_SIZE)
  1283. return (ptr);
  1285. p = imalloc(size);
  1286. if (p)
  1287. memcpy(p, ptr, PTR_SIZE);
  1288. ifree(ptr);
  1289. return (p);
  1290. }
  1291. index = ptr2index(ptr);
  1293. if (index < malloc_pageshift) {
  1294. wrtwarning("junk pointer, too low to make sense");
  1295. return (NULL);
  1296. }
  1297. if (index > last_index) {
  1298. wrtwarning("junk pointer, too high to make sense");
  1299. return (NULL);
  1300. }
  1301. pdir_lookup(index, &pi);
  1302. #ifdef MALLOC_EXTRA_SANITY
  1303. pidx = PI_IDX(index);
  1304. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  1305. wrterror("(ES): mapped pages not found in directory");
  1306. errno = EFAULT;
  1307. return (NULL);
  1308. }
  1309. #endif /* MALLOC_EXTRA_SANITY */
  1310. if (pi != last_dir) {
  1311. prev_dir = last_dir;
  1312. last_dir = pi;
  1313. }
  1314. pd = pi->base;
  1315. mp = &pd[PI_OFF(index)];
  1317. if (*mp == MALLOC_FIRST) { /* Page allocation */
  1319. /* Check the pointer */
  1320. if ((u_long) ptr & malloc_pagemask) {
  1321. wrtwarning("modified (page-) pointer");
  1322. return (NULL);
  1323. }
  1324. /* Find the size in bytes */
  1325. i = index;
  1326. if (!PI_OFF(++i)) {
  1327. pi = pi->next;
  1328. if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
  1329. pi = NULL;
  1330. if (pi != NULL)
  1331. pd = pi->base;
  1332. }
  1333. for (osize = malloc_pagesize;
  1334.     pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
  1335. osize += malloc_pagesize;
  1336. if (!PI_OFF(++i)) {
  1337. pi = pi->next;
  1338. if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
  1339. pi = NULL;
  1340. if (pi != NULL)
  1341. pd = pi->base;
  1342. }
  1343. }
  1345. if (!malloc_realloc && size <= osize &&
  1346.     size > osize - malloc_pagesize) {
  1347. if (malloc_junk)
  1348. memset((char *)ptr + size, SOME_JUNK, osize - size);
  1349. return (ptr); /* ..don't do anything else. */
  1350. }
  1351. } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */
  1353. /* Check the pointer for sane values */
  1354. if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
  1355. wrtwarning("modified (chunk-) pointer");
  1356. return (NULL);
  1357. }
  1358. /* Find the chunk index in the page */
  1359. i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;
  1361. /* Verify that it isn't a free chunk already */
  1362. if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
  1363. wrtwarning("chunk is already free");
  1364. return (NULL);
  1365. }
  1366. osize = (*mp)->size;
  1368. if (!malloc_realloc && size <= osize &&
  1369.     (size > osize / 2 || osize == malloc_minsize)) {
  1370. if (malloc_junk)
  1371. memset((char *) ptr + size, SOME_JUNK, osize - size);
  1372. return (ptr); /* ..don't do anything else. */
  1373. }
  1374. } else {
  1375. wrtwarning("irealloc: pointer to wrong page");
  1376. return (NULL);
  1377. }
  1379. p = imalloc(size);
  1381. if (p != NULL) {
  1382. /* copy the lesser of the two sizes, and free the old one */
  1383. /* Don't move from/to 0 sized region !!! */
  1384. if (osize != 0 && size != 0) {
  1385. if (osize < size)
  1386. memcpy(p, ptr, osize);
  1387. else
  1388. memcpy(p, ptr, size);
  1389. }
  1390. ifree(ptr);
  1391. }
  1392. return (p);
  1393. }
  1395. /*
  1396.  * Free a sequence of pages
  1397.  */
  1398. static __inline__ void
  1399. free_pages(void *ptr, u_long index, struct pginfo * info)
  1400. {
  1401. u_long i, pidx, lidx;
  1402. size_t l, cachesize = 0;
  1403. struct pginfo **pd;
  1404. struct pdinfo *pi, *spi;
  1405. struct pgfree *pf, *pt = NULL;
  1406. caddr_t tail;
  1408. if (info == MALLOC_FREE) {
  1409. wrtwarning("page is already free");
  1410. return;
  1411. }
  1412. if (info != MALLOC_FIRST) {
  1413. wrtwarning("free_pages: pointer to wrong page");
  1414. return;
  1415. }
  1416. if ((u_long) ptr & malloc_pagemask) {
  1417. wrtwarning("modified (page-) pointer");
  1418. return;
  1419. }
  1420. /* Count how many pages and mark them free at the same time */
  1421. pidx = PI_IDX(index);
  1422. pdir_lookup(index, &pi);
  1423. #ifdef MALLOC_EXTRA_SANITY
  1424. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  1425. wrterror("(ES): mapped pages not found in directory");
  1426. errno = EFAULT;
  1427. return;
  1428. }
  1429. #endif /* MALLOC_EXTRA_SANITY */
  1431. spi = pi; /* Save page index for start of region. */
  1433. pd = pi->base;
  1434. pd[PI_OFF(index)] = MALLOC_FREE;
  1435. i = 1;
  1436. if (!PI_OFF(index + i)) {
  1437. pi = pi->next;
  1438. if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
  1439. pi = NULL;
  1440. else
  1441. pd = pi->base;
  1442. }
  1443. while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
  1444. pd[PI_OFF(index + i)] = MALLOC_FREE;
  1445. i++;
  1446. if (!PI_OFF(index + i)) {
  1447. if ((pi = pi->next) == NULL ||
  1448.     PD_IDX(pi->dirnum) != PI_IDX(index + i))
  1449. pi = NULL;
  1450. else
  1451. pd = pi->base;
  1452. }
  1453. }
  1455. l = i << malloc_pageshift;
  1457. if (malloc_junk)
  1458. memset(ptr, SOME_JUNK, l);
  1460. malloc_used -= l;
  1461. malloc_guarded -= malloc_guard;
  1462. if (malloc_guard) {
  1463. #ifdef MALLOC_EXTRA_SANITY
  1464. if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) {
  1465. wrterror("(ES): hole in mapped pages directory");
  1466. errno = EFAULT;
  1467. return;
  1468. }
  1469. #endif /* MALLOC_EXTRA_SANITY */
  1470. pd[PI_OFF(index + i)] = MALLOC_FREE;
  1471. l += malloc_guard;
  1472. }
  1473. tail = (caddr_t)ptr + l;
  1475. if (malloc_hint)
  1476. madvise(ptr, l, MADV_FREE);
  1478. if (malloc_freeprot)
  1479. mprotect(ptr, l, PROT_NONE);
  1481. /* Add to free-list. */
  1482. if (px == NULL && (px = malloc_bytes(sizeof *px)) == NULL)
  1483. goto not_return;
  1484. px->page = ptr;
  1485. px->pdir = spi;
  1486. px->size = l;
  1488. if (free_list.next == NULL) {
  1489. /* Nothing on free list, put this at head. */
  1490. px->next = NULL;
  1491. px->prev = &free_list;
  1492. free_list.next = px;
  1493. pf = px;
  1494. px = NULL;
  1495. } else {
  1496. /*
  1497.  * Find the right spot, leave pf pointing to the modified
  1498.  * entry.
  1499.  */
  1501. /* Race ahead here, while calculating cache size. */
  1502. for (pf = free_list.next;
  1503.     (caddr_t)ptr > ((caddr_t)pf->page + pf->size)
  1504.     && pf->next != NULL;
  1505.     pf = pf->next)
  1506. cachesize += pf->size;
  1508. /* Finish cache size calculation. */
  1509. pt = pf;
  1510. while (pt) {
  1511. cachesize += pt->size;
  1512. pt = pt->next;
  1513. }
  1515. if ((caddr_t)pf->page > tail) {
  1516. /* Insert before entry */
  1517. px->next = pf;
  1518. px->prev = pf->prev;
  1519. pf->prev = px;
  1520. px->prev->next = px;
  1521. pf = px;
  1522. px = NULL;
  1523. } else if (((caddr_t)pf->page + pf->size) == ptr) {
  1524. /* Append to the previous entry. */
  1525. cachesize -= pf->size;
  1526. pf->size += l;
  1527. if (pf->next != NULL &&
  1528.     pf->next->page == ((caddr_t)pf->page + pf->size)) {
  1529. /* And collapse the next too. */
  1530. pt = pf->next;
  1531. pf->size += pt->size;
  1532. pf->next = pt->next;
  1533. if (pf->next != NULL)
  1534. pf->next->prev = pf;
  1535. }
  1536. } else if (pf->page == tail) {
  1537. /* Prepend to entry. */
  1538. cachesize -= pf->size;
  1539. pf->size += l;
  1540. pf->page = ptr;
  1541. pf->pdir = spi;
  1542. } else if (pf->next == NULL) {
  1543. /* Append at tail of chain. */
  1544. px->next = NULL;
  1545. px->prev = pf;
  1546. pf->next = px;
  1547. pf = px;
  1548. px = NULL;
  1549. } else {
  1550. wrterror("freelist is destroyed");
  1551. errno = EFAULT;
  1552. return;
  1553. }
  1554. }
  1556. if (pf->pdir != last_dir) {
  1557. prev_dir = last_dir;
  1558. last_dir = pf->pdir;
  1559. }
  1561. /* Return something to OS ? */
  1562. if (pf->size > (malloc_cache - cachesize)) {
  1564. /*
  1565.  * Keep the cache intact.  Notice that the '>' above guarantees that
  1566.  * the pf will always have at least one page afterwards.
  1567.  */
  1568. if (munmap((char *) pf->page + (malloc_cache - cachesize),
  1569.     pf->size - (malloc_cache - cachesize)) != 0)
  1570. goto not_return;
  1571. tail = (caddr_t)pf->page + pf->size;
  1572. lidx = ptr2index(tail) - 1;
  1573. pf->size = malloc_cache - cachesize;
  1575. index = ptr2index((caddr_t)pf->page + pf->size);
  1577. pidx = PI_IDX(index);
  1578. if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
  1579. prev_dir = NULL; /* Will be wiped out below ! */
  1581. for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
  1582.     pi = pi->next)
  1583. ;
  1585. spi = pi;
  1586. if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
  1587. pd = pi->base;
  1589. for (i = index; i <= lidx;) {
  1590. if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
  1591. pd[PI_OFF(i)] = MALLOC_NOT_MINE;
  1592. #ifdef MALLOC_EXTRA_SANITY
  1593. if (!PD_OFF(pi->dirnum)) {
  1594. wrterror("(ES): pages directory underflow");
  1595. errno = EFAULT;
  1596. return;
  1597. }
  1598. #endif /* MALLOC_EXTRA_SANITY */
  1599. pi->dirnum--;
  1600. }
  1601. #ifdef MALLOC_EXTRA_SANITY
  1602. else
  1603. wrtwarning("(ES): page already unmapped");
  1604. #endif /* MALLOC_EXTRA_SANITY */
  1605. i++;
  1606. if (!PI_OFF(i)) {
  1607. /*
  1608.  * If no page in that dir, free
  1609.  * directory page.
  1610.  */
  1611. if (!PD_OFF(pi->dirnum)) {
  1612. /* Remove from list. */
  1613. if (spi == pi)
  1614. spi = pi->prev;
  1615. if (pi->prev != NULL)
  1616. pi->prev->next = pi->next;
  1617. if (pi->next != NULL)
  1618. pi->next->prev = pi->prev;
  1619. pi = pi->next;
  1620. munmap(pd, malloc_pagesize);
  1621. } else
  1622. pi = pi->next;
  1623. if (pi == NULL ||
  1624.     PD_IDX(pi->dirnum) != PI_IDX(i))
  1625. break;
  1626. pd = pi->base;
  1627. }
  1628. }
  1629. if (pi && !PD_OFF(pi->dirnum)) {
  1630. /* Resulting page dir is now empty. */
  1631. /* Remove from list. */
  1632. if (spi == pi) /* Update spi only if first. */
  1633. spi = pi->prev;
  1634. if (pi->prev != NULL)
  1635. pi->prev->next = pi->next;
  1636. if (pi->next != NULL)
  1637. pi->next->prev = pi->prev;
  1638. pi = pi->next;
  1639. munmap(pd, malloc_pagesize);
  1640. }
  1641. }
  1642. if (pi == NULL && malloc_brk == tail) {
  1643. /* Resize down the malloc upper boundary. */
  1644. last_index = index - 1;
  1645. malloc_brk = index2ptr(index);
  1646. }
  1648. /* XXX: We could realloc/shrink the pagedir here I guess. */
  1649. if (pf->size == 0) { /* Remove from free-list as well. */
  1650. if (px)
  1651. ifree(px);
  1652. if ((px = pf->prev) != &free_list) {
  1653. if (pi == NULL && last_index == (index - 1)) {
  1654. if (spi == NULL) {
  1655. malloc_brk = NULL;
  1656. i = 11;
  1657. } else {
  1658. pd = spi->base;
  1659. if (PD_IDX(spi->dirnum) < pidx)
  1660. index =
  1661.     ((PD_IDX(spi->dirnum) + 1) *
  1662.     pdi_mod) - 1;
  1663. for (pi = spi, i = index;
  1664.     pd[PI_OFF(i)] == MALLOC_NOT_MINE;
  1665.     i--)
  1666. #ifdef MALLOC_EXTRA_SANITY
  1667. if (!PI_OFF(i)) {
  1668. pi = pi->prev;
  1669. if (pi == NULL || i == 0)
  1670. break;
  1671. pd = pi->base;
  1672. i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
  1673. }
  1674. #else /* !MALLOC_EXTRA_SANITY */
  1675. {
  1676. }
  1677. #endif /* MALLOC_EXTRA_SANITY */
  1678. malloc_brk = index2ptr(i + 1);
  1679. }
  1680. last_index = i;
  1681. }
  1682. if ((px->next = pf->next) != NULL)
  1683. px->next->prev = px;
  1684. } else {
  1685. if ((free_list.next = pf->next) != NULL)
  1686. free_list.next->prev = &free_list;
  1687. }
  1688. px = pf;
  1689. last_dir = prev_dir;
  1690. prev_dir = NULL;
  1691. }
  1692. }
  1693. not_return:
  1694. if (pt != NULL)
  1695. ifree(pt);
  1696. }
  1698. /*
  1699.  * Free a chunk, and possibly the page it's on, if the page becomes empty.
  1700.  */
  1702. /* ARGSUSED */
  1703. static __inline__ void
  1704. free_bytes(void *ptr, u_long index, struct pginfo * info)
  1705. {
  1706. struct pginfo **mp, **pd;
  1707. struct pdinfo *pi;
  1708. #ifdef MALLOC_EXTRA_SANITY
  1709. u_long pidx;
  1710. #endif /* MALLOC_EXTRA_SANITY */
  1711. void *vp;
  1712. long i;
  1713. (void) index;
  1715. /* Find the chunk number on the page */
  1716. i = ((u_long) ptr & malloc_pagemask) >> info->shift;
  1718. if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
  1719. wrtwarning("modified (chunk-) pointer");
  1720. return;
  1721. }
  1722. if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
  1723. wrtwarning("chunk is already free");
  1724. return;
  1725. }
  1726. if (malloc_junk && info->size != 0)
  1727. memset(ptr, SOME_JUNK, (size_t)info->size);
  1729. info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
  1730. info->free++;
  1732. if (info->size != 0)
  1733. mp = page_dir + info->shift;
  1734. else
  1735. mp = page_dir;
  1737. if (info->free == 1) {
  1738. /* Page became non-full */
  1740. /* Insert in address order */
  1741. while (*mp != NULL && (*mp)->next != NULL &&
  1742.     (*mp)->next->page < info->page)
  1743. mp = &(*mp)->next;
  1744. info->next = *mp;
  1745. *mp = info;
  1746. return;
  1747. }
  1748. if (info->free != info->total)
  1749. return;
  1751. /* Find & remove this page in the queue */
  1752. while (*mp != info) {
  1753. mp = &((*mp)->next);
  1754. #ifdef MALLOC_EXTRA_SANITY
  1755. if (!*mp) {
  1756. wrterror("(ES): Not on queue");
  1757. errno = EFAULT;
  1758. return;
  1759. }
  1760. #endif /* MALLOC_EXTRA_SANITY */
  1761. }
  1762. *mp = info->next;
  1764. /* Free the page & the info structure if need be */
  1765. pdir_lookup(ptr2index(info->page), &pi);
  1766. #ifdef MALLOC_EXTRA_SANITY
  1767. pidx = PI_IDX(ptr2index(info->page));
  1768. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  1769. wrterror("(ES): mapped pages not found in directory");
  1770. errno = EFAULT;
  1771. return;
  1772. }
  1773. #endif /* MALLOC_EXTRA_SANITY */
  1774. if (pi != last_dir) {
  1775. prev_dir = last_dir;
  1776. last_dir = pi;
  1777. }
  1778. pd = pi->base;
  1779. pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
  1781. /* If the page was mprotected, unprotect it before releasing it */
  1782. if (info->size == 0)
  1783. mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);
  1785. vp = info->page; /* Order is important ! */
  1786. if (vp != (void *) info)
  1787. ifree(info);
  1788. ifree(vp);
  1789. }
  1791. static void
  1792. ifree(void *ptr)
  1793. {
  1794. struct pginfo *info, **pd;
  1795. u_long index;
  1796. #ifdef MALLOC_EXTRA_SANITY
  1797. u_long pidx;
  1798. #endif /* MALLOC_EXTRA_SANITY */
  1799. struct pdinfo *pi;
  1801. if (!malloc_started) {
  1802. wrtwarning("malloc() has never been called");
  1803. return;
  1804. }
  1805. /* If we're already sinking, don't make matters any worse. */
  1806. if (suicide)
  1807. return;
  1809. if (malloc_ptrguard && PTR_ALIGNED(ptr))
  1810. ptr = (char *) ptr - PTR_GAP;
  1812. index = ptr2index(ptr);
  1814. if (index < malloc_pageshift) {
  1815. warnx("(%p)", ptr);
  1816. wrtwarning("ifree: junk pointer, too low to make sense");
  1817. return;
  1818. }
  1819. if (index > last_index) {
  1820. warnx("(%p)", ptr);
  1821. wrtwarning("ifree: junk pointer, too high to make sense");
  1822. return;
  1823. }
  1824. pdir_lookup(index, &pi);
  1825. #ifdef MALLOC_EXTRA_SANITY
  1826. pidx = PI_IDX(index);
  1827. if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
  1828. wrterror("(ES): mapped pages not found in directory");
  1829. errno = EFAULT;
  1830. return;
  1831. }
  1832. #endif /* MALLOC_EXTRA_SANITY */
  1833. if (pi != last_dir) {
  1834. prev_dir = last_dir;
  1835. last_dir = pi;
  1836. }
  1837. pd = pi->base;
  1838. info = pd[PI_OFF(index)];
  1840. if (info < MALLOC_MAGIC)
  1841. free_pages(ptr, index, info);
  1842. else
  1843. free_bytes(ptr, index, info);
  1845. /* does not matter if malloc_bytes fails */
  1846. if (px == NULL)
  1847. px = malloc_bytes(sizeof *px);
  1849. return;
  1850. }
  1852. /*
  1853.  * Common function for handling recursion.  Only
  1854.  * print the error message once, to avoid making the problem
  1855.  * potentially worse.
  1856.  */
  1857. static void
  1858. malloc_recurse(void)
  1859. {
  1860. static int noprint;
  1862. if (noprint == 0) {
  1863. noprint = 1;
  1864. wrtwarning("recursive call");
  1865. }
  1866. malloc_active--;
  1867. _MALLOC_UNLOCK();
  1868. errno = EDEADLK;
  1869. }
  1871. /*
  1872.  * These are the public exported interface routines.
  1873.  */
  1874. void *
  1875. malloc(size_t size)
  1876. {
  1877. void *r;
  1879. if (!align)
  1880. _MALLOC_LOCK();
  1881. malloc_func = " in malloc():";
  1882. if (malloc_active++) {
  1883. malloc_recurse();
  1884. return (NULL);
  1885. }
  1886. r = imalloc(size);
  1887. UTRACE(0, size, r);
  1888. malloc_active--;
  1889. if (!align)
  1890. _MALLOC_UNLOCK();
  1891. if (malloc_xmalloc && r == NULL) {
  1892. wrterror("out of memory");
  1893. errno = ENOMEM;
  1894. }
  1895. return (r);
  1896. }
  1898. void
  1899. free(void *ptr)
  1900. {
  1901. /* This is legal. XXX quick path */
  1902. if (ptr == NULL)
  1903. return;
  1905. _MALLOC_LOCK();
  1906. malloc_func = " in free():";
  1907. if (malloc_active++) {
  1908. malloc_recurse();
  1909. return;
  1910. }
  1911. ifree(ptr);
  1912. UTRACE(ptr, 0, 0);
  1913. malloc_active--;
  1914. _MALLOC_UNLOCK();
  1915. return;
  1916. }
  1918. void *
  1919. realloc(void *ptr, size_t size)
  1920. {
  1921. void *r;
  1923. _MALLOC_LOCK();
  1924. malloc_func = " in realloc():";
  1925. if (malloc_active++) {
  1926. malloc_recurse();
  1927. return (NULL);
  1928. }
  1930. if (ptr == NULL)
  1931. r = imalloc(size);
  1932. else
  1933. r = irealloc(ptr, size);
  1935. UTRACE(ptr, size, r);
  1936. malloc_active--;
  1937. _MALLOC_UNLOCK();
  1938. if (malloc_xmalloc && r == NULL) {
  1939. wrterror("out of memory");
  1940. errno = ENOMEM;
  1941. }
  1942. return (r);
  1943. }
  1945. #ifndef SIZE_MAX
  1946. //#if defined(__i386__)||defined(__arm__)||defined(__powerpc__)
  1947. //#define SIZE_MAX 0xffffffff
  1948. //#endif
  1949. //#if defined(__x86_64__)
  1950. //#define SIZE_MAX 0xffffffffffffffff
  1951. //#endif
  1952. #define SIZE_MAX SIZE_T_MAX
  1953. #endif
  1955. void *
  1956. calloc(size_t num, size_t size)
  1957. {
  1958. void *p;
  1960. if (num && SIZE_MAX / num < size) {
  1961. fprintf(stderr,"OOOOPS");
  1962. errno = ENOMEM;
  1963. return NULL;
  1964. }
  1965. size *= num;
  1966. p = malloc(size);
  1967. if (p)
  1968. memset(p, 0, size);
  1969. return(p);
  1970. }
  1972. static int ispowerof2 (size_t a) {
  1973. size_t b;
  1974. for (b = 1ULL << (sizeof(size_t)*NBBY - 1); b > 1; b >>= 1)
  1975.   if (b == a)
  1976. return 1;
  1977. return 0;
  1978. }
  1980. int posix_memalign(void **memptr, size_t alignment, size_t size)
  1981. {
  1982. void *r;
  1983. if ((alignment < PTR_SIZE) || (alignment%PTR_SIZE != 0)) return EINVAL;
  1984. if (!ispowerof2(alignment)) return EINVAL;
  1985. if (alignment < malloc_minsize) alignment = malloc_minsize;
  1986. size_t max = alignment > size ? alignment : size;
  1987. if (alignment <= malloc_pagesize)
  1988. r = malloc(max);
  1989. else {
  1990. _MALLOC_LOCK();
  1991. align = 1;
  1992. g_alignment = alignment;
  1993. r = malloc(size);
  1994. align=0;
  1995. _MALLOC_UNLOCK();
  1996. }
  1997. *memptr = r;
  1998. if (!r) return ENOMEM;
  1999. return 0;
  2000. }
  2002. void *memalign(size_t boundary, size_t size)
  2003. {
  2004. void *r;
  2005. posix_memalign(&r, boundary, size);
  2006. return r;
  2007. }
  2009. void *valloc(size_t size)
  2010. {
  2011. void *r;
  2012. posix_memalign(&r, malloc_pagesize, size);
  2013. return r;
  2014. }
  2016. size_t malloc_good_size(size_t size)
  2017. {
  2018. if (size == 0) {
  2019. return 1;
  2020. } else if (size <= malloc_maxsize) {
  2021. int i, j;
  2022. /* round up to the nearest power of 2, with same approach
  2023.  * as malloc_bytes() uses. */
  2024. j = 1;
  2025. i = size - 1;
  2026. while (i >>= 1)
  2027. j++;
  2028. return ((size_t)1) << j;
  2029. } else {
  2030. return pageround(size);
  2031. }
  2032. }