free.c 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274
  1. /*
  2. * libc/stdlib/malloc/free.c -- free function
  3. *
  4. * Copyright (C) 2002,03 NEC Electronics Corporation
  5. * Copyright (C) 2002,03 Miles Bader <miles@gnu.org>
  6. *
  7. * This file is subject to the terms and conditions of the GNU Lesser
  8. * General Public License. See the file COPYING.LIB in the main
  9. * directory of this archive for more details.
  10. *
  11. * Written by Miles Bader <miles@gnu.org>
  12. */
  13. #include <stdlib.h>
  14. #include <unistd.h>
  15. #include <sys/mman.h>
  16. libc_hidden_proto(munmap)
  17. libc_hidden_proto(sbrk)
  18. #include "malloc.h"
  19. #include "heap.h"
  20. #ifdef HEAP_USE_LOCKING
  21. #define free_to_heap(mem, heap, lck) __free_to_heap(mem, heap, lck)
  22. #else
  23. #define free_to_heap(mem, heap, lck) __free_to_heap(mem, heap)
  24. #endif
  25. static void
  26. __free_to_heap (void *mem, struct heap_free_area **heap
  27. #ifdef HEAP_USE_LOCKING
  28. , malloc_mutex_t *heap_lock
  29. #endif
  30. )
  31. {
  32. size_t size;
  33. struct heap_free_area *fa;
  34. /* Check for special cases. */
  35. if (unlikely (! mem))
  36. return;
  37. /* Normal free. */
  38. MALLOC_DEBUG (1, "free: 0x%lx (base = 0x%lx, total_size = %d)",
  39. (long)mem, (long)MALLOC_BASE (mem), MALLOC_SIZE (mem));
  40. size = MALLOC_SIZE (mem);
  41. mem = MALLOC_BASE (mem);
  42. __heap_lock (heap_lock);
  43. /* Put MEM back in the heap, and get the free-area it was placed in. */
  44. fa = __heap_free (heap, mem, size);
  45. /* See if the free-area FA has grown big enough that it should be
  46. unmapped. */
  47. if (HEAP_FREE_AREA_SIZE (fa) < MALLOC_UNMAP_THRESHOLD)
  48. /* Nope, nothing left to do, just release the lock. */
  49. __heap_unlock (heap_lock);
  50. else
  51. /* Yup, try to unmap FA. */
  52. {
  53. unsigned long start = (unsigned long)HEAP_FREE_AREA_START (fa);
  54. unsigned long end = (unsigned long)HEAP_FREE_AREA_END (fa);
  55. #ifndef MALLOC_USE_SBRK
  56. # ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
  57. struct malloc_mmb *mmb, *prev_mmb;
  58. unsigned long mmb_start, mmb_end;
  59. # else /* !__UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
  60. unsigned long unmap_start, unmap_end;
  61. # endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
  62. #endif /* !MALLOC_USE_SBRK */
  63. #ifdef MALLOC_USE_SBRK
  64. /* Get the sbrk lock so that the two possible calls to sbrk below
  65. are guaranteed to be contiguous. */
  66. __malloc_lock_sbrk ();
  67. /* When using sbrk, we only shrink the heap from the end. It would
  68. be possible to allow _both_ -- shrinking via sbrk when possible,
  69. and otherwise shrinking via munmap, but this results in holes in
  70. memory that prevent the brk from every growing back down; since
  71. we only ever grow the heap via sbrk, this tends to produce a
  72. continuously growing brk (though the actual memory is unmapped),
  73. which could eventually run out of address space. Note that
  74. `sbrk(0)' shouldn't normally do a system call, so this test is
  75. reasonably cheap. */
  76. if ((void *)end != sbrk (0))
  77. {
  78. MALLOC_DEBUG (-1, "not unmapping: 0x%lx - 0x%lx (%ld bytes)",
  79. start, end, end - start);
  80. __malloc_unlock_sbrk ();
  81. __heap_unlock (heap_lock);
  82. return;
  83. }
  84. #endif
  85. MALLOC_DEBUG (0, "unmapping: 0x%lx - 0x%lx (%ld bytes)",
  86. start, end, end - start);
  87. /* Remove FA from the heap. */
  88. __heap_delete (heap, fa);
  89. if (__heap_is_empty (heap))
  90. /* We want to avoid the heap from losing all memory, so reserve
  91. a bit. This test is only a heuristic -- the existance of
  92. another free area, even if it's smaller than
  93. MALLOC_MIN_SIZE, will cause us not to reserve anything. */
  94. {
  95. /* Put the reserved memory back in the heap; we assume that
  96. MALLOC_UNMAP_THRESHOLD is greater than MALLOC_MIN_SIZE, so
  97. we use the latter unconditionally here. */
  98. __heap_free (heap, (void *)start, MALLOC_MIN_SIZE);
  99. start += MALLOC_MIN_SIZE;
  100. }
  101. #ifdef MALLOC_USE_SBRK
  102. /* Release the heap lock; we're still holding the sbrk lock. */
  103. __heap_unlock (heap_lock);
  104. /* Lower the brk. */
  105. sbrk (start - end);
  106. /* Release the sbrk lock too; now we hold no locks. */
  107. __malloc_unlock_sbrk ();
  108. #else /* !MALLOC_USE_SBRK */
  109. # ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
  110. /* Using the uClinux broken munmap, we have to only munmap blocks
  111. exactly as we got them from mmap, so scan through our list of
  112. mmapped blocks, and return them in order. */
  113. MALLOC_MMB_DEBUG (1, "walking mmb list for region 0x%x[%d]...",
  114. start, end - start);
  115. prev_mmb = 0;
  116. mmb = __malloc_mmapped_blocks;
  117. while (mmb
  118. && ((mmb_end = (mmb_start = (unsigned long)mmb->mem) + mmb->size)
  119. <= end))
  120. {
  121. MALLOC_MMB_DEBUG (1, "considering mmb at 0x%x: 0x%x[%d]",
  122. (unsigned)mmb, mmb_start, mmb_end - mmb_start);
  123. if (mmb_start >= start
  124. /* If the space between START and MMB_START is non-zero, but
  125. too small to return to the heap, we can't unmap MMB. */
  126. && (start == mmb_start
  127. || mmb_start - start > HEAP_MIN_FREE_AREA_SIZE))
  128. {
  129. struct malloc_mmb *next_mmb = mmb->next;
  130. if (mmb_end != end && mmb_end + HEAP_MIN_FREE_AREA_SIZE > end)
  131. /* There's too little space left at the end to deallocate
  132. this block, so give up. */
  133. break;
  134. MALLOC_MMB_DEBUG (1, "unmapping mmb at 0x%x: 0x%x[%d]",
  135. (unsigned)mmb, mmb_start, mmb_end - mmb_start);
  136. if (mmb_start != start)
  137. /* We're going to unmap a part of the heap that begins after
  138. start, so put the intervening region back into the heap. */
  139. {
  140. MALLOC_MMB_DEBUG (0, "putting intervening region back into heap: 0x%x[%d]",
  141. start, mmb_start - start);
  142. __heap_free (heap, (void *)start, mmb_start - start);
  143. }
  144. MALLOC_MMB_DEBUG_INDENT (-1);
  145. /* Unlink MMB from the list. */
  146. if (prev_mmb)
  147. prev_mmb->next = next_mmb;
  148. else
  149. __malloc_mmapped_blocks = next_mmb;
  150. /* Start searching again from the end of this block. */
  151. start = mmb_end;
  152. /* We have to unlock the heap before we recurse to free the mmb
  153. descriptor, because we might be unmapping from the mmb
  154. heap. */
  155. __heap_unlock (heap_lock);
  156. /* Release the descriptor block we used. */
  157. free_to_heap (mmb, &__malloc_mmb_heap, &__malloc_mmb_heap_lock);
  158. /* Do the actual munmap. */
  159. munmap ((void *)mmb_start, mmb_end - mmb_start);
  160. __heap_lock (heap_lock);
  161. # ifdef __UCLIBC_HAS_THREADS__
  162. /* In a multi-threaded program, it's possible that PREV_MMB has
  163. been invalidated by another thread when we released the
  164. heap lock to do the munmap system call, so just start over
  165. from the beginning of the list. It sucks, but oh well;
  166. it's probably not worth the bother to do better. */
  167. prev_mmb = 0;
  168. mmb = __malloc_mmapped_blocks;
  169. # else
  170. mmb = next_mmb;
  171. # endif
  172. }
  173. else
  174. {
  175. prev_mmb = mmb;
  176. mmb = mmb->next;
  177. }
  178. MALLOC_MMB_DEBUG_INDENT (-1);
  179. }
  180. if (start != end)
  181. /* Hmm, well there's something we couldn't unmap, so put it back
  182. into the heap. */
  183. {
  184. MALLOC_MMB_DEBUG (0, "putting tail region back into heap: 0x%x[%d]",
  185. start, end - start);
  186. __heap_free (heap, (void *)start, end - start);
  187. }
  188. /* Finally release the lock for good. */
  189. __heap_unlock (heap_lock);
  190. MALLOC_MMB_DEBUG_INDENT (-1);
  191. # else /* !__UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
  192. /* MEM/LEN may not be page-aligned, so we have to page-align them,
  193. and return any left-over bits on the end to the heap. */
  194. unmap_start = MALLOC_ROUND_UP_TO_PAGE_SIZE (start);
  195. unmap_end = MALLOC_ROUND_DOWN_TO_PAGE_SIZE (end);
  196. /* We have to be careful that any left-over bits are large enough to
  197. return. Note that we _don't check_ to make sure there's room to
  198. grow/shrink the start/end by another page, we just assume that
  199. the unmap threshold is high enough so that this is always safe
  200. (i.e., it should probably be at least 3 pages). */
  201. if (unmap_start > start)
  202. {
  203. if (unmap_start - start < HEAP_MIN_FREE_AREA_SIZE)
  204. unmap_start += MALLOC_PAGE_SIZE;
  205. __heap_free (heap, (void *)start, unmap_start - start);
  206. }
  207. if (end > unmap_end)
  208. {
  209. if (end - unmap_end < HEAP_MIN_FREE_AREA_SIZE)
  210. unmap_end -= MALLOC_PAGE_SIZE;
  211. __heap_free (heap, (void *)unmap_end, end - unmap_end);
  212. }
  213. /* Release the heap lock before we do the system call. */
  214. __heap_unlock (heap_lock);
  215. if (unmap_end > unmap_start)
  216. /* Finally, actually unmap the memory. */
  217. munmap ((void *)unmap_start, unmap_end - unmap_start);
  218. # endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
  219. #endif /* MALLOC_USE_SBRK */
  220. }
  221. MALLOC_DEBUG_INDENT (-1);
  222. }
  223. void
  224. free (void *mem)
  225. {
  226. free_to_heap (mem, &__malloc_heap, &__malloc_heap_lock);
  227. }