Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. MALLOC_ALIGNMENT = 8    ; must be power of two not less than 8, not greater than 4096
  2. CHUNK_ALIGN_MASK = MALLOC_ALIGNMENT - 1
  3.  
  4. ; -----------------------  Chunk representations ------------------------
  5. ;
  6. ;  (The following includes lightly edited explanations by Colin Plumb.)
  7. ;
  8. ;  The malloc_chunk declaration below is misleading (but accurate and
  9. ;  necessary).  It declares a "view" into memory allowing access to
  10. ;  necessary fields at known offsets from a given base.
  11. ;
  12. ;  Chunks of memory are maintained using a `boundary tag' method as
  13. ;  originally described by Knuth.  (See the paper by Paul Wilson
  14. ;  ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such
  15. ;  techniques.)  Sizes of free chunks are stored both in the front of
  16. ;  each chunk and at the end.  This makes consolidating fragmented
  17. ;  chunks into bigger chunks fast.  The head fields also hold bits
  18. ;  representing whether chunks are free or in use.
  19. ;
  20. ;  Here are some pictures to make it clearer.  They are "exploded" to
  21. ;  show that the state of a chunk can be thought of as extending from
  22. ;  the high 31 bits of the head field of its header through the
  23. ;  prev_foot and PINUSE_BIT bit of the following chunk header.
  24. ;
  25. ;  A chunk that's in use looks like:
  26. ;
  27. ;   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  28. ;           | Size of previous chunk (if P = 0)                             |
  29. ;           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  30. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
  31. ;         | Size of this chunk                                         1| +-+
  32. ;   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  33. ;         |                                                               |
  34. ;         +-                                                             -+
  35. ;         |                                                               |
  36. ;         +-                                                             -+
  37. ;         |                                                               :
  38. ;         +-      size - sizeof(size_t) available payload bytes          -+
  39. ;         :                                                               |
  40. ; chunk-> +-                                                             -+
  41. ;         |                                                               |
  42. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  43. ;       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
  44. ;       | Size of next chunk (may or may not be in use)               | +-+
  45. ; mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  46. ;
  47. ;    And if it's free, it looks like this:
  48. ;
  49. ;   chunk-> +-                                                             -+
  50. ;           | User payload (must be in use, or we would have merged!)       |
  51. ;           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  52. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
  53. ;         | Size of this chunk                                         0| +-+
  54. ;   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  55. ;         | Next pointer                                                  |
  56. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  57. ;         | Prev pointer                                                  |
  58. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  59. ;         |                                                               :
  60. ;         +-      size - sizeof(struct chunk) unused bytes               -+
  61. ;         :                                                               |
  62. ; chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  63. ;         | Size of this chunk                                            |
  64. ;         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  65. ;       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
  66. ;       | Size of next chunk (must be in use, or we would have merged)| +-+
  67. ; mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  68. ;       |                                                               :
  69. ;       +- User payload                                                -+
  70. ;       :                                                               |
  71. ;       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  72. ;                                                                     |0|
  73. ;                                                                     +-+
  74. ;  Note that since we always merge adjacent free chunks, the chunks
  75. ;  adjacent to a free chunk must be in use.
  76. ;
  77. ;  Given a pointer to a chunk (which can be derived trivially from the
  78. ;  payload pointer) we can, in O(1) time, find out whether the adjacent
  79. ;  chunks are free, and if so, unlink them from the lists that they
  80. ;  are on and merge them with the current chunk.
  81. ;
  82. ;  Chunks always begin on even word boundaries, so the mem portion
  83. ;  (which is returned to the user) is also on an even word boundary, and
  84. ;  thus at least double-word aligned.
  85. ;
  86. ;  The P (PINUSE_BIT) bit, stored in the unused low-order bit of the
  87. ;  chunk size (which is always a multiple of two words), is an in-use
  88. ;  bit for the *previous* chunk.  If that bit is *clear*, then the
  89. ;  word before the current chunk size contains the previous chunk
  90. ;  size, and can be used to find the front of the previous chunk.
  91. ;  The very first chunk allocated always has this bit set, preventing
  92. ;  access to non-existent (or non-owned) memory. If pinuse is set for
  93. ;  any given chunk, then you CANNOT determine the size of the
  94. ;  previous chunk, and might even get a memory addressing fault when
  95. ;  trying to do so.
  96. ;
  97. ;  The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of
  98. ;  the chunk size redundantly records whether the current chunk is
  99. ;  inuse (unless the chunk is mmapped). This redundancy enables usage
  100. ;  checks within free and realloc, and reduces indirection when freeing
  101. ;  and consolidating chunks.
  102. ;
  103. ;  Each freshly allocated chunk must have both cinuse and pinuse set.
  104. ;  That is, each allocated chunk borders either a previously allocated
  105. ;  and still in-use chunk, or the base of its memory arena. This is
  106. ;  ensured by making all allocations from the `lowest' part of any
  107. ;  found chunk.  Further, no free chunk physically borders another one,
  108. ;  so each free chunk is known to be preceded and followed by either
  109. ;  inuse chunks or the ends of memory.
  110. ;
  111. ;  Note that the `foot' of the current chunk is actually represented
  112. ;  as the prev_foot of the NEXT chunk. This makes it easier to
  113. ;  deal with alignments etc but can be very confusing when trying
  114. ;  to extend or adapt this code.
  115. ;
  116. ;  The exceptions to all this are
  117. ;
  118. ;     1. The special chunk `top' is the top-most available chunk (i.e.,
  119. ;        the one bordering the end of available memory). It is treated
  120. ;        specially.  Top is never included in any bin, is used only if
  121. ;        no other chunk is available. In effect,
  122. ;        the top chunk is treated as larger (and thus less well
  123. ;        fitting) than any other available chunk.  The top chunk
  124. ;        doesn't update its trailing size field since there is no next
  125. ;        contiguous chunk that would have to index off it. However,
  126. ;        space is still allocated for it (TOP_FOOT_SIZE) to enable
  127. ;        separation or merging when space is extended.
  128. ;
  129. ;     2. Chunks allocated via mmap, have both cinuse and pinuse bits
  130. ;        cleared in their head fields.  Because they are allocated
  131. ;        one-by-one, each must carry its own prev_foot field, which is
  132. ;        also used to hold the offset this chunk has within its mmapped
  133. ;        region, which is needed to preserve alignment. Each mmapped
  134. ;        chunk is trailed by the first two fields of a fake next-chunk
  135. ;        for sake of usage checks.
  136. ;
  137. struct malloc_chunk
  138. prev_foot       dd      ?       ; size of previous chunk (if free)
  139. head            dd      ?       ; size and inuse bits
  140. data            rd      0       ; label for data (if busy)
  141. fd              dd      ?       ; pointer to data in next malloc_chunk (if free)
  142. bk              dd      ?       ; pointer to data in prev malloc_chunk (if free)
  143. ends
  144. mchunk_prev_foot = malloc_chunk.prev_foot - malloc_chunk.data
  145. mchunk_head      = malloc_chunk.head      - malloc_chunk.data
  146. mchunk_fd        = malloc_chunk.fd        - malloc_chunk.data
  147. mchunk_bk        = malloc_chunk.bk        - malloc_chunk.data
  148.  
  149. ; ------------------- Chunks sizes and alignments -----------------------
  150. MCHUNK_SIZE = sizeof.malloc_chunk
  151. if FOOTERS
  152. CHUNK_OVERHEAD = 8
  153. else
  154. CHUNK_OVERHEAD = 4
  155. end if
  156. ; MMapped chunks need a second word of overhead ...
  157. MMAP_CHUNK_OVERHEAD = 8
  158. ; ... and additional padding for fake next-chunk at foot
  159. MMAP_FOOT_PAD = 16
  160. ; The smallest size we can malloc is an aligned minimal chunk
  161. MIN_CHUNK_SIZE = (MCHUNK_SIZE + CHUNK_ALIGN_MASK) and not CHUNK_ALIGN_MASK
  162. ; Bounds on request (not chunk) sizes.
  163. MAX_REQUEST = (-MIN_CHUNK_SIZE) * 4
  164. MIN_REQUEST = MIN_CHUNK_SIZE - CHUNK_OVERHEAD
  165.  
  166. ; ------------------ Operations on head and foot fields -----------------
  167. ;  The head field of a chunk is or'ed with PINUSE_BIT when previous
  168. ;  adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in
  169. ;  use, unless mmapped, in which case both bits are cleared.
  170. ;
  171. ;  FLAG4_BIT is not used by this malloc, but might be useful in extensions.
  172. PINUSE_BIT = 1
  173. CINUSE_BIT = 2
  174. FLAG4_BIT = 4
  175. INUSE_BITS = PINUSE_BIT + CINUSE_BIT
  176. FLAG_BITS = PINUSE_BIT + CINUSE_BIT + FLAG4_BIT
  177. ; Head value for fenceposts
  178. FENCEPOST_HEAD = 4 + INUSE_BITS
  179.  
  180. ; ---------------------- Overlaid data structures -----------------------
  181. ;  When chunks are not in use, they are treated as nodes of either
  182. ;  lists or trees.
  183. ;
  184. ;  "Small"  chunks are stored in circular doubly-linked lists, and look
  185. ;  like this:
  186. ;
  187. ;    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  188. ;            |             Size of previous chunk                            |
  189. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  190. ;    `head:' |             Size of chunk, in bytes                         |P|
  191. ;      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  192. ;            |             Forward pointer to next chunk in list             |
  193. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  194. ;            |             Back pointer to previous chunk in list            |
  195. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  196. ;            |             Unused space (may be 0 bytes long)                .
  197. ;            .                                                               .
  198. ;            .                                                               |
  199. ;nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  200. ;    `foot:' |             Size of chunk, in bytes                           |
  201. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  202. ;
  203. ;  Larger chunks are kept in a form of bitwise digital trees (aka
  204. ;  tries) keyed on chunksizes.  Because malloc_tree_chunks are only for
  205. ;  free chunks greater than 256 bytes, their size doesn't impose any
  206. ;  constraints on user chunk sizes.  Each node looks like:
  207. ;
  208. ;    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  209. ;            |             Size of previous chunk                            |
  210. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  211. ;    `head:' |             Size of chunk, in bytes                         |P|
  212. ;      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  213. ;            |             Forward pointer to next chunk of same size        |
  214. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  215. ;            |             Back pointer to previous chunk of same size       |
  216. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  217. ;            |             Pointer to left child (child[0])                  |
  218. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  219. ;            |             Pointer to right child (child[1])                 |
  220. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  221. ;            |             Pointer to parent                                 |
  222. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  223. ;            |             bin index of this chunk                           |
  224. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  225. ;            |             Unused space                                      .
  226. ;            .                                                               |
  227. ;nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  228. ;    `foot:' |             Size of chunk, in bytes                           |
  229. ;            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  230. ;
  231. ;  Each tree holding treenodes is a tree of unique chunk sizes.  Chunks
  232. ;  of the same size are arranged in a circularly-linked list, with only
  233. ;  the oldest chunk (the next to be used, in our FIFO ordering)
  234. ;  actually in the tree.  (Tree members are distinguished by a non-null
  235. ;  parent pointer.)  If a chunk with the same size an an existing node
  236. ;  is inserted, it is linked off the existing node using pointers that
  237. ;  work in the same way as fd/bk pointers of small chunks.
  238. ;
  239. ;  Each tree contains a power of 2 sized range of chunk sizes (the
  240. ;  smallest is 0x100 <= x < 0x180), which is is divided in half at each
  241. ;  tree level, with the chunks in the smaller half of the range (0x100
  242. ;  <= x < 0x140 for the top nose) in the left subtree and the larger
  243. ;  half (0x140 <= x < 0x180) in the right subtree.  This is, of course,
  244. ;  done by inspecting individual bits.
  245. ;
  246. ;  Using these rules, each node's left subtree contains all smaller
  247. ;  sizes than its right subtree.  However, the node at the root of each
  248. ;  subtree has no particular ordering relationship to either.  (The
  249. ;  dividing line between the subtree sizes is based on trie relation.)
  250. ;  If we remove the last chunk of a given size from the interior of the
  251. ;  tree, we need to replace it with a leaf node.  The tree ordering
  252. ;  rules permit a node to be replaced by any leaf below it.
  253. ;
  254. ;  The smallest chunk in a tree (a common operation in a best-fit
  255. ;  allocator) can be found by walking a path to the leftmost leaf in
  256. ;  the tree.  Unlike a usual binary tree, where we follow left child
  257. ;  pointers until we reach a null, here we follow the right child
  258. ;  pointer any time the left one is null, until we reach a leaf with
  259. ;  both child pointers null. The smallest chunk in the tree will be
  260. ;  somewhere along that path.
  261. ;
  262. ;  The worst case number of steps to add, find, or remove a node is
  263. ;  bounded by the number of bits differentiating chunks within
  264. ;  bins. Under current bin calculations, this ranges from 6 up to 21
  265. ;  (for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case
  266. ;  is of course much better.
  267. ;
  268. ;  All large chunks which have been extended after last call to sys_trim
  269. ;  are kept in a single-linked list with head inside malloc_state.
  270. ;  For a chunk not in the list, release_fd/release_bk point to itself.
  271. struct malloc_tree_chunk malloc_chunk
  272. left_child      dd      ?       ; pointer to malloc_tree_chunk.data
  273. right_child     dd      ?       ; pointer to malloc_tree_chunk.data
  274. parent          dd      ?       ; pointer to malloc_tree_chunk.data
  275. index           dd      ?
  276. ends
  277. tchunk_left_child  = malloc_tree_chunk.left_child  - malloc_chunk.data
  278. tchunk_right_child = malloc_tree_chunk.right_child - malloc_chunk.data
  279. tchunk_parent      = malloc_tree_chunk.parent      - malloc_chunk.data
  280. tchunk_index       = malloc_tree_chunk.index       - malloc_chunk.data
  281. tchunk_release_fd  = mchunk_prev_foot - 8
  282. tchunk_release_bk  = tchunk_release_fd + 4
  283.  
  284. ; ----------------------------- Segments --------------------------------
  285. ;
  286. ;  Each malloc space may include non-contiguous segments, held in a
  287. ;  list headed by an embedded malloc_segment record representing the
  288. ;  top-most space. Large chunks that are directly allocated by mmap are not
  289. ;  included in this list. They are instead independently created and
  290. ;  destroyed without otherwise keeping track of them.
  291. ;
  292. ;  Except for the top-most segment of an mstate, each segment record
  293. ;  is kept at the tail of its segment. Segments are added by pushing
  294. ;  segment records onto the list headed by &mstate.seg for the
  295. ;  containing mstate.
  296. ;
  297. struct malloc_segment
  298. base            dd      ?       ; base address
  299. size            dd      ?       ; allocated size
  300. next            dd      ?       ; pointer to next malloc_segment
  301. ends
  302.  
  303. ; ---------------------------- malloc_state -----------------------------
  304. ;   A malloc_state holds all of the bookkeeping for a space.
  305. ;   The main fields are:
  306. ;
  307. ;  Top
  308. ;    The topmost chunk of the currently active segment. Its size is
  309. ;    cached in topsize.  The actual size of topmost space is
  310. ;    topsize+TOP_FOOT_SIZE, which includes space reserved for adding
  311. ;    fenceposts and segment records if necessary when getting more
  312. ;    space from the system.
  313. ;
  314. ;  Designated victim (dv)
  315. ;    This is the preferred chunk for servicing small requests that
  316. ;    don't have exact fits.  It is normally the chunk split off most
  317. ;    recently to service another small request.  Its size is cached in
  318. ;    dvsize. The link fields of this chunk are not maintained since it
  319. ;    is not kept in a bin.
  320. ;
  321. ;  SmallBins
  322. ;    An array of bin headers for free chunks.  These bins hold chunks
  323. ;    with sizes less than MIN_LARGE_SIZE bytes. Each bin contains
  324. ;    chunks of all the same size, spaced 8 bytes apart.  To simplify
  325. ;    use in double-linked lists, each bin header acts as a malloc_chunk
  326. ;    pointing to the real first node, if it exists (else pointing to
  327. ;    itself).  This avoids special-casing for headers.  But to avoid
  328. ;    waste, we allocate only the fd/bk pointers of bins, and then use
  329. ;    repositioning tricks to treat these as the fields of a chunk.
  330. ;
  331. ;  TreeBins
  332. ;    Treebins are pointers to the roots of trees holding a range of
  333. ;    sizes. There are 2 equally spaced treebins for each power of two
  334. ;    from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything
  335. ;    larger.
  336. ;
  337. ;  Bin maps
  338. ;    There is one bit map for small bins ("smallmap") and one for
  339. ;    treebins ("treemap).  Each bin sets its bit when non-empty, and
  340. ;    clears the bit when empty.  Bit operations are then used to avoid
  341. ;    bin-by-bin searching -- nearly all "search" is done without ever
  342. ;    looking at bins that won't be selected.  The bit maps
  343. ;    conservatively use 32 bits per map word, even if on 64bit system.
  344. ;    For a good description of some of the bit-based techniques used
  345. ;    here, see Henry S. Warren Jr's book "Hacker's Delight" (and
  346. ;    supplement at http://hackersdelight.org/). Many of these are
  347. ;    intended to reduce the branchiness of paths through malloc etc, as
  348. ;    well as to reduce the number of memory locations read or written.
  349. ;
  350. ;  Segments
  351. ;    A list of segments headed by an embedded malloc_segment record
  352. ;    representing the initial space.
  353. ;
  354. ;  Magic tag
  355. ;    A cross-check field that should always hold same value as malloc_magic.
  356. ;
  357. ;  Max allowed footprint
  358. ;    The maximum allowed bytes to allocate from system (zero means no limit)
  359. ;
  360. ;  Flags
  361. ;    Bits recording whether to use locks
  362. ;
  363. ;  Statistics
  364. ;    Each space keeps track of current and maximum system memory.
  365. ;
  366. ;  Trim support
  367. ;    Fields holding the amount of unused topmost memory that should trigger
  368. ;    trimming, and a counter to force periodic scanning to release unused
  369. ;    non-topmost segments.
  370. ;
  371. ;  Locking
  372. ;    If USE_LOCKS is defined, the "mutex" lock is acquired and released
  373. ;    around every public call using this mspace.
  374. ;typedef struct malloc_segment  msegment;
  375. ;typedef struct malloc_segment* msegmentptr;
  376. NSMALLBINS              =       32
  377. NTREEBINS               =       32
  378. SMALLBIN_SHIFT          =       3
  379. SMALLBIN_WIDTH          =       1 shl SMALLBIN_SHIFT
  380. TREEBIN_SHIFT           =       8
  381. MIN_LARGE_SIZE          =       1 shl TREEBIN_SHIFT
  382. assert MIN_LARGE_SIZE = NSMALLBINS * SMALLBIN_WIDTH
  383. MAX_SMALL_SIZE          =       MIN_LARGE_SIZE - 1
  384. MAX_SMALL_REQUEST       =       MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD
  385.  
  386. struct malloc_state
  387. smallmap        dd      ?       ; bitmap for non-empty small bins
  388. treemap         dd      ?       ; bitmap for non-empty tree bins
  389. dvsize          dd      ?       ; designated victim size
  390. topsize         dd      ?       ; size of free top area
  391. dv              dd      ?       ; pointer to malloc_chunk.data of designated victim
  392. top             dd      ?       ; pointer to malloc_chunk.data of top area
  393. topmax          dd      ?       ; maximum value of top after prev release check
  394. release_checks  dd      ?       ; counter before next release check
  395. release_list    rd      2       ; list of malloc_tree_chunk with pages to release
  396. mmap_list       rd      2       ; list of mmapped chunks
  397. magic           dd      ?       ; for FOOTERS
  398. smallbins       rd      NSMALLBINS*2    ; pointers to malloc_chunk.data
  399. treebins        rd      NTREEBINS       ; pointers to malloc_tree_chunk.data
  400. footprint       dd      ?
  401. max_footprint   dd      ?
  402. footprint_limit dd      ?       ; zero means no limit
  403. mmap_threshold  dd      ?
  404. segment_size    dd      ?
  405. mflags          dd      ?
  406. mutex           dd      ?
  407. seg             malloc_segment
  408. ends
  409. ; Bits for malloc_state.mflags
  410. USE_LOCK_BIT = 2
  411. ;
  412. TOP_FOOT_SIZE = (-8) and CHUNK_ALIGN_MASK + (sizeof.malloc_segment + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) and not CHUNK_ALIGN_MASK + MIN_CHUNK_SIZE
  413. SYS_ALLOC_PADDING = TOP_FOOT_SIZE + MALLOC_ALIGNMENT
  414.  
  415. ; in: ebp -> malloc_state
  416. ; out: eax -> malloc_segment
  417. macro segment_holding address
  418. {
  419.         lea     eax, [ebp+malloc_state.seg]
  420. @@:
  421.         mov     ecx, address
  422.         sub     ecx, [eax+malloc_segment.base]
  423.         cmp     ecx, [eax+malloc_segment.size]
  424.         jb      @f
  425.         mov     eax, [eax+malloc_segment.next]
  426.         test    eax, eax
  427.         jnz     @b
  428. @@:
  429. }
  430.  
  431. ; in: ebp -> malloc_state
  432. macro lock_heap
  433. {
  434. local .done
  435.         test    [ebp+malloc_state.mflags], USE_LOCK_BIT
  436.         jz      .done
  437. ; TODO: use mutex when it will be available in kernel API
  438. @@:
  439.         mov     eax, 1
  440.         xchg    [ebp+malloc_state.mutex], eax
  441.         test    eax, eax
  442.         jz      .done
  443.         mov     eax, 68
  444.         mov     ebx, 1
  445.         call    FS_SYSCALL_PTR
  446.         jmp     @b
  447. .done:
  448. }
  449. ; in: ebp -> malloc_state
  450. macro unlock_heap
  451. {
  452. local .done
  453.         test    [ebp+malloc_state.mflags], USE_LOCK_BIT
  454.         jz      .done
  455. ; TODO: use mutex when it will be available in kernel API
  456.         mov     [ebp+malloc_state.mutex], 0
  457. .done:
  458. }
  459.  
  460. ; ---------------------------- Indexing Bins ----------------------------
  461. MIN_SMALL_INDEX = MIN_CHUNK_SIZE shr SMALLBIN_SHIFT
  462. ; in: sizereg = size, must be >= 1 shl TREEBIN_SHIFT
  463. ; out: ecx = index, sizereg = size << leftshift_for_tree_index
  464. macro compute_tree_index sizereg
  465. {
  466.         mov     ecx, NTREEBINS-1
  467.         cmp     sizereg, 0xC000 shl TREEBIN_SHIFT
  468.         jae     @f
  469.         bsr     ecx, sizereg
  470.         ror     sizereg, cl
  471.         adc     ecx, ecx
  472.         lea     sizereg, [(sizereg-1)*2]
  473.         sub     ecx, TREEBIN_SHIFT*2
  474. @@:
  475. }
  476. ; ----------------------- Runtime Check Support -------------------------
  477. macro mark_inuse_foot where
  478. {
  479. if FOOTERS
  480.         mov     ebx, ebp
  481.         xor     ebx, [malloc_magic]
  482.         mov     [where+mchunk_prev_foot], ebx
  483. end if
  484. }
  485.  
  486. ; ----------------------- Operations on smallbins -----------------------
  487. ; Link a free chunk into a smallbin
  488. ; in: ebp -> malloc_state, esi -> malloc_chunk.data, edx = size
  489. macro insert_small_chunk_noshift
  490. {
  491.         bts     [ebp+malloc_state.smallmap], edx
  492.         mov     ecx, [ebp+malloc_state.smallbins+edx*8+mchunk_fd]
  493.         lea     edx, [ebp+malloc_state.smallbins+edx*8]
  494.         mov     [ecx+mchunk_bk], esi
  495.         mov     [edx+mchunk_fd], esi
  496.         mov     [esi+mchunk_fd], ecx
  497.         mov     [esi+mchunk_bk], edx
  498. }
  499. macro insert_small_chunk
  500. {
  501.         shr     edx, SMALLBIN_SHIFT
  502.         insert_small_chunk_noshift
  503. }
  504.  
  505. ; Unlink a chunk from a smallbin
  506. ; in: ebp -> malloc_state, eax -> malloc_chunk.data, edx = size
  507. macro unlink_small_chunk
  508. {
  509.         mov     ecx, [eax+mchunk_fd]
  510.         mov     ebx, [eax+mchunk_bk]
  511.         cmp     [ecx+mchunk_bk], eax
  512.         jnz     heap_corrupted
  513.         cmp     [ebx+mchunk_fd], eax
  514.         jnz     heap_corrupted
  515.         mov     [ecx+mchunk_bk], ebx
  516.         mov     [ebx+mchunk_fd], ecx
  517.         cmp     ecx, ebx
  518.         jnz     @f
  519.         shr     edx, SMALLBIN_SHIFT
  520.         btr     [ebp+malloc_state.smallmap], edx
  521. @@:
  522. }
  523.  
  524. ; Unlink the first chunk from a smallbin
  525. ; in: ebp -> malloc_state, edx -> list header, eax -> malloc_chunk.data
  526. ; in: ecx = smallbin index
  527. macro unlink_first_small_chunk
  528. {
  529.         mov     ebx, [eax+mchunk_fd]
  530.         cmp     [ebx+mchunk_bk], eax
  531.         jnz     heap_corrupted
  532.         mov     [ebx+mchunk_bk], edx
  533.         mov     [edx+mchunk_fd], ebx
  534.         cmp     edx, ebx
  535.         jnz     @f
  536.         btr     [ebp+malloc_state.smallmap], ecx
  537. @@:
  538. }
  539.  
  540. ; Replace dv node, binning the old one
  541. ; Used only when dvsize known to be small
  542. ; in: ebp -> malloc_state, ecx = chunk size, edx -> malloc_chunk.data
  543. macro replace_dv
  544. {
  545.         mov     esi, [ebp+malloc_state.dv]
  546.         mov     [ebp+malloc_state.dv], edx
  547.         mov     edx, [ebp+malloc_state.dvsize]
  548.         mov     [ebp+malloc_state.dvsize], ecx
  549.         shr     edx, SMALLBIN_SHIFT
  550.         jz      @f
  551.         insert_small_chunk_noshift ; ebp,esi,edx
  552. @@:
  553. }
  554.  
  555. ; ------------------------- Operations on trees -------------------------
  556. ; Insert chunk into tree
  557. ; in: ebp -> malloc_state, esi -> malloc_chunk.data, edx = size
  558. macro insert_large_chunk return_action
  559. {
  560. local .not_first, .loop, .exact_size
  561.         mov     edi, edx
  562.         compute_tree_index edx
  563.         lea     ebx, [ebp+malloc_state.treebins+ecx*4]
  564.         mov     [esi+tchunk_index], ecx
  565.         mov     dword [esi+tchunk_left_child], 0
  566.         mov     dword [esi+tchunk_right_child], 0
  567.         bts     [ebp+malloc_state.treemap], ecx
  568.         jc      .not_first
  569.         mov     [ebx], esi
  570.         mov     [esi+tchunk_parent], ebx
  571.         mov     [esi+mchunk_fd], esi
  572.         mov     [esi+mchunk_bk], esi
  573.         return_action
  574. .not_first:
  575.         mov     ebx, [ebx]
  576. .loop:
  577.         mov     ecx, [ebx+mchunk_head]
  578.         and     ecx, not FLAG_BITS
  579.         cmp     ecx, edi
  580.         jz      .exact_size
  581.         xor     ecx, ecx
  582.         add     edx, edx
  583.         adc     ecx, ecx
  584.         lea     ecx, [ebx+tchunk_left_child+ecx*4]
  585.         cmp     dword [ecx], 0
  586.         jz      @f
  587.         mov     ebx, [ecx]
  588.         jmp     .loop
  589. @@:
  590.         mov     [ecx], esi
  591.         mov     [esi+tchunk_parent], ebx
  592.         mov     [esi+mchunk_fd], esi
  593.         mov     [esi+mchunk_bk], esi
  594.         return_action
  595. .exact_size:
  596.         mov     edx, [ebx+mchunk_fd]
  597.         mov     [edx+mchunk_bk], esi
  598.         mov     [ebx+mchunk_fd], esi
  599.         mov     [esi+mchunk_fd], edx
  600.         mov     [esi+mchunk_bk], ebx
  601.         mov     dword [esi+tchunk_parent], 0
  602.         return_action
  603. }
  604.  
  605. ;  Unlink steps:
  606. ;
  607. ;  1. If x is a chained node, unlink it from its same-sized fd/bk links
  608. ;     and choose its bk node as its replacement.
  609. ;  2. If x was the last node of its size, but not a leaf node, it must
  610. ;     be replaced with a leaf node (not merely one with an open left or
  611. ;     right), to make sure that lefts and rights of descendents
  612. ;     correspond properly to bit masks.  We use the rightmost descendent
  613. ;     of x.  We could use any other leaf, but this is easy to locate and
  614. ;     tends to counteract removal of leftmosts elsewhere, and so keeps
  615. ;     paths shorter than minimally guaranteed.  This doesn't loop much
  616. ;     because on average a node in a tree is near the bottom.
  617. ;  3. If x is the base of a chain (i.e., has parent links) relink
  618. ;     x's parent and children to x's replacement (or null if none).
  619.  
  620. ; in: ebp -> malloc_state, eax -> malloc_tree_chunk.data
  621. ; destroys ebx,edx,esi, keeps eax,ecx
  622. macro unlink_large_chunk
  623. {
  624. local .last, .common1, .find_rightmost_child, .done, .advance_right, .remove_root
  625.         mov     esi, [eax+tchunk_parent]
  626.         cmp     [eax+mchunk_bk], eax
  627.         jz      .last
  628.         mov     edx, [eax+mchunk_fd]
  629.         mov     ebx, [eax+mchunk_bk]
  630.         cmp     [edx+mchunk_bk], eax
  631.         jnz     heap_corrupted
  632.         cmp     [ebx+mchunk_fd], eax
  633.         jnz     heap_corrupted
  634.         mov     [edx+mchunk_bk], ebx
  635.         mov     [ebx+mchunk_fd], edx
  636.         jmp     .common1
  637. .last:
  638.         mov     ebx, [eax+tchunk_right_child]
  639.         lea     edx, [eax+tchunk_right_child]
  640.         test    ebx, ebx
  641.         jnz     .find_rightmost_child
  642.         mov     ebx, [eax+tchunk_left_child]
  643.         lea     edx, [eax+tchunk_left_child]
  644.         test    ebx, ebx
  645.         jz      .common1
  646. .find_rightmost_child:
  647.         cmp     dword [ebx+tchunk_right_child], 0
  648.         jnz     .advance_right
  649.         cmp     dword [ebx+tchunk_left_child], 0
  650.         jz      @f
  651.         lea     edx, [ebx+tchunk_left_child]
  652.         mov     ebx, [ebx+tchunk_left_child]
  653.         jmp     .find_rightmost_child
  654. .advance_right:
  655.         lea     edx, [ebx+tchunk_right_child]
  656.         mov     ebx, [ebx+tchunk_right_child]
  657.         jmp     .find_rightmost_child
  658. @@:
  659.         mov     dword [edx], 0
  660. .common1:
  661.         test    esi, esi
  662.         jz      .done
  663.         mov     edx, [eax+tchunk_index]
  664.         cmp     [ebp+malloc_state.treebins+edx*4], eax
  665.         jz      .remove_root
  666.         xor     edx, edx
  667.         cmp     [esi+tchunk_left_child], eax
  668.         setnz   dl
  669.         mov     [esi+tchunk_left_child+edx*4], ebx
  670.         jmp     @f
  671. .remove_root:
  672.         mov     [ebp+malloc_state.treebins+edx*4], ebx
  673.         test    ebx, ebx
  674.         jnz     @f
  675.         btr     [ebp+malloc_state.treemap], edx
  676. @@:
  677.         test    ebx, ebx
  678.         jz      .done
  679.         mov     [ebx+tchunk_parent], esi
  680.         cmp     dword [eax+tchunk_left_child], 0
  681.         jz      @f
  682.         mov     edx, [eax+tchunk_left_child]
  683.         mov     [ebx+tchunk_left_child], edx
  684.         mov     [edx+tchunk_parent], ebx
  685. @@:
  686.         cmp     dword [eax+tchunk_right_child], 0
  687.         jz      @f
  688.         mov     edx, [eax+tchunk_right_child]
  689.         mov     [ebx+tchunk_right_child], edx
  690.         mov     [edx+tchunk_parent], ebx
  691. @@:
  692. .done:
  693. }
  694.  
  695. ; Relays to large vs small bin operations
  696. ; in: ebp -> malloc_state, esi -> malloc_chunk.data, edx = size
  697. macro insert_chunk return_action
  698. {
  699. local .large
  700.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  701.         jae     .large
  702.         insert_small_chunk      ; ebp, esi, edx
  703.         return_action
  704. .large:
  705.         insert_large_chunk return_action        ; ebp, esi, edx
  706. }
  707.  
  708. ; in: ebp -> malloc_state, eax -> malloc_chunk.data, edx = size
  709. macro unlink_chunk
  710. {
  711. local .large, .common
  712.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  713.         jae     .large
  714.         unlink_small_chunk      ; ebp, eax, edx
  715.         jmp     .common
  716. .large:
  717.         unlink_large_chunk      ; ebp, eax
  718. .common:
  719. }
  720.  
  721. ; -----------------------  Direct-mmapping chunks -----------------------
  722. ; Since a system call is used in these functions anyway,
  723. ; the speed is not of primary value here.
  724.  
  725. ;   Directly mmapped chunks are set up with an offset to the start of
  726. ;  the mmapped region stored in the prev_foot field of the chunk. This
  727. ;  allows reconstruction of the required argument to MUNMAP when freed,
  728. ;  and also allows adjustment of the returned chunk to meet alignment
  729. ;  requirements (especially in memalign).
  730.  
  731. ; in: ebp -> malloc_state, ecx = nb
  732. ; out: eax -> allocated block on success, 0 on failure
  733. ; destroys: eax, ebx, ecx
  734. assert MALLOC_ALIGNMENT <= 4096 ; it is important here
  735. proc mmap_alloc
  736.         add     ecx, 8*4 + CHUNK_ALIGN_MASK + 0xFFF
  737.         jc      .error
  738.         and     ecx, not 0xFFF
  739.         cmp     [ebp+malloc_state.footprint_limit], 0
  740.         jz      @f
  741.         mov     eax, [ebp+malloc_state.footprint]
  742.         add     eax, ecx
  743.         jc      .error
  744.         cmp     eax, [ebp+malloc_state.footprint_limit]
  745.         ja      .error
  746. @@:
  747.         mov     eax, 68
  748.         mov     ebx, 12
  749.         call    FS_SYSCALL_PTR
  750.         test    eax, eax
  751.         jz      .error
  752.         lea     ebx, [ebp+malloc_state.mmap_list]
  753.         mov     edx, [ebp+malloc_state.mmap_list]
  754.         cmp     [edx+4], ebx
  755.         jnz     heap_corrupted
  756.         mov     [ebx], eax
  757.         mov     [edx+4], eax
  758.         mov     [eax], edx
  759.         mov     [eax+4], ebx
  760.         add     eax, ((-16) and CHUNK_ALIGN_MASK) + 16
  761.         lea     edx, [ecx-((-16) and CHUNK_ALIGN_MASK)-8-MMAP_FOOT_PAD]
  762.         mov     dword [eax+mchunk_prev_foot], ((-16) and CHUNK_ALIGN_MASK) + 16
  763.         mov     [eax+mchunk_head], edx
  764.         mark_inuse_foot eax+edx
  765.         mov     dword [eax+edx+mchunk_head], FENCEPOST_HEAD
  766.         mov     dword [eax+edx+4+mchunk_head], 0
  767.         add     ecx, [ebp+malloc_state.footprint]
  768.         mov     [ebp+malloc_state.footprint], ecx
  769.         cmp     ecx, [ebp+malloc_state.max_footprint]
  770.         jb      @f
  771.         mov     [ebp+malloc_state.max_footprint], ecx
  772. @@:
  773.         ret
  774. .error:
  775.         xor     eax, eax
  776.         ret
  777. endp
  778.  
  779. ; in: ebp -> malloc_state, ecx = nb, edx -> old malloc_chunk.data
  780. ; in: ebx = can_move: if zero, fail unless realloc in place is possible
  781. proc mmap_resize
  782.         mov     eax, [edx+mchunk_head]
  783.         cmp     ecx, NSMALLBINS shl SMALLBIN_SHIFT
  784.         jb      .error
  785.         sub     eax, ecx
  786.         jc      .realloc
  787.         cmp     eax, 4
  788.         jb      .realloc
  789.         cmp     eax, 0x2000
  790.         ja      .realloc
  791.         mov     eax, edx
  792.         ret
  793. .realloc:
  794.         test    ebx, ebx
  795.         jz      .error
  796.         sub     edx, [edx+mchunk_prev_foot]
  797.         mov     eax, [edx]
  798.         mov     ebx, [edx+4]
  799.         cmp     [eax+4], edx
  800.         jnz     heap_corrupted
  801.         cmp     [ebx], edx
  802.         jnz     heap_corrupted
  803.         mov     [eax+4], ebx
  804.         mov     [ebx], eax
  805.         mov     eax, 68
  806.         mov     ebx, 20
  807.         add     ecx, 8*4 + CHUNK_ALIGN_MASK + 0xFFF
  808.         and     ecx, not 0xFFF
  809.         call    FS_SYSCALL_PTR
  810.         test    eax, eax
  811.         jz      .error
  812.         mov     ebx, [eax]
  813.         mov     [ebx+4], eax
  814.         mov     ebx, [eax+4]
  815.         mov     [ebx], eax
  816.         add     eax, ((-16) and CHUNK_ALIGN_MASK)+16
  817.         mov     edx, [eax+mchunk_head]
  818.         add     edx, ((-16) and CHUNK_ALIGN_MASK)+8+MMAP_FOOT_PAD
  819.         lea     ebx, [ecx-((-16) and CHUNK_ALIGN_MASK)-8-MMAP_FOOT_PAD]
  820.         mov     [eax+mchunk_head], ebx
  821.         mark_inuse_foot eax+ecx-((-16) and CHUNK_ALIGN_MASK)-8-MMAP_FOOT_PAD
  822.         mov     dword [eax+ecx-((-16) and CHUNK_ALIGN_MASK)-8-MMAP_FOOT_PAD+mchunk_head], FENCEPOST_HEAD
  823.         mov     dword [eax+ecx-((-16) and CHUNK_ALIGN_MASK)-8-MMAP_FOOT_PAD+4+mchunk_head], 0
  824.         add     ecx, [ebp+malloc_state.footprint]
  825.         sub     ecx, edx
  826.         mov     [ebp+malloc_state.footprint], ecx
  827.         cmp     ecx, [ebp+malloc_state.max_footprint]
  828.         jb      @f
  829.         mov     [ebp+malloc_state.max_footprint], ecx
  830. @@:
  831.         ret
  832. .error:
  833.         xor     eax, eax
  834.         ret
  835. endp
  836.  
  837. ; -------------------------- mspace management --------------------------
  838.  
  839. ; Initialize top chunk and its size
  840. ; in: eax -> malloc_state, ebx -> malloc_chunk.data for top, ecx = size
  841. ; ebx must be aligned to MALLOC_ALIGNMENT
  842. macro init_top
  843. {
  844.         mov     [eax+malloc_state.top], ebx
  845.         mov     [eax+malloc_state.topmax], ebx
  846.         mov     [eax+malloc_state.topsize], ecx
  847.         lea     edx, [ecx+PINUSE_BIT]
  848.         mov     [ebx+mchunk_head], edx
  849.         mov     dword [ebx+ecx+mchunk_head], TOP_FOOT_SIZE
  850. }
  851.  
  852. ; Same as init_top, but return the previous top
  853. ; in: ebp -> malloc_state, eax -> malloc_chunk.data for top, ecx = size
  854. ; out: edx -> malloc_chunk.data for old top
  855. macro reinit_top
  856. {
  857.         lea     edx, [ecx+PINUSE_BIT]
  858.         mov     [eax+mchunk_head], edx
  859.         mov     dword [eax+ecx+mchunk_head], TOP_FOOT_SIZE
  860.         mov     edx, [ebp+malloc_state.top]
  861.         mov     [ebp+malloc_state.top], eax
  862.         mov     [ebp+malloc_state.topmax], eax
  863.         mov     [ebp+malloc_state.topsize], ecx
  864. }
  865.  
  866. ; Initialize bins for a new mstate that is otherwise zeroed out
  867. ; in: eax -> malloc_state
  868. macro init_bins
  869. {
  870.         lea     ebx, [eax+malloc_state.smallbins]
  871.         mov     edx, NSMALLBINS
  872. @@:
  873.         mov     [ebx+mchunk_fd], ebx
  874.         mov     [ebx+mchunk_bk], ebx
  875.         add     ebx, 8
  876.         dec     edx
  877.         jnz     @b
  878. }
  879.  
  880. ; Add a segment to hold a new noncontiguous region
  881. ; in: ebp -> malloc_state, eax = segment base, ecx = segment size
  882. malloc_seg_chunk_size = (sizeof.malloc_segment + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) and not CHUNK_ALIGN_MASK
  883. macro add_segment
  884. {
  885. local .nothing, .large
  886.         push    edi
  887.         push    eax ecx
  888. ; Ensure alignment for top
  889.         add     eax, 8 + ((-8) and CHUNK_ALIGN_MASK)
  890.         sub     ecx, TOP_FOOT_SIZE + ((-8) and CHUNK_ALIGN_MASK)
  891. ; reset top to new space
  892.         reinit_top
  893.         segment_holding edx
  894.         mov     ecx, [eax+malloc_segment.base]
  895.         add     ecx, [eax+malloc_segment.size]
  896.         lea     ebx, [edx+MIN_CHUNK_SIZE]
  897.         lea     eax, [ecx - malloc_seg_chunk_size - MALLOC_ALIGNMENT]
  898.         cmp     eax, ebx
  899.         jae     @f
  900.         mov     eax, edx
  901. @@:
  902. ; Set up segment record
  903.         mov     dword [eax+mchunk_head], malloc_seg_chunk_size+PINUSE_BIT+CINUSE_BIT
  904.         mark_inuse_foot eax+malloc_seg_chunk_size
  905. ; Push current record
  906.         mov     ebx, [ebp+malloc_state.seg.base]
  907.         mov     [eax+malloc_segment.base], ebx
  908.         mov     ebx, [ebp+malloc_state.seg.size]
  909.         mov     [eax+malloc_segment.size], ebx
  910.         mov     ebx, [ebp+malloc_state.seg.next]
  911.         mov     [eax+malloc_segment.next], ebx
  912.         popd    [ebp+malloc_state.seg.size] [ebp+malloc_state.seg.base]
  913.         mov     [ebp+malloc_state.seg.next], eax
  914. ; Insert trailing fenceposts
  915.         mov     esi, edx
  916.         sub     edx, eax
  917.         lea     edi, [eax+malloc_seg_chunk_size+mchunk_head]
  918.         mov     eax, FENCEPOST_HEAD
  919.         sub     ecx, edi
  920.         shr     ecx, 2
  921.         rep stosd
  922. ; Insert the rest of old top into a bin as an ordinary free chunk
  923.         neg     edx
  924.         jz      .nothing
  925.         and     dword [esi+edx+mchunk_head], not PINUSE_BIT
  926.         lea     ecx, [edx+PINUSE_BIT]
  927.         mov     [esi+mchunk_head], ecx
  928.         mov     [esi+edx+mchunk_prev_foot], edx
  929.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  930.         jb      .small
  931.         lea     ecx, [esi+edx]
  932.         mov     [ecx+tchunk_release_fd], ecx
  933.         mov     [ecx+tchunk_release_bk], ecx
  934.         insert_large_chunk <jmp .nothing>       ; ebp, esi, edx
  935. .small:
  936.         insert_small_chunk      ; ebp, esi, edx
  937. .nothing:
  938.         pop     edi
  939. }
  940.  
  941. ; -------------------------- System allocation --------------------------
  942.  
  943. ; Get memory from system using MMAP
  944. ; in: ebp -> malloc_state, esi = size
  945.  
  946. ; Allocate a new segment and a chunk inside that segment.
  947. ; Algorithm of segment size calculation:
  948. ; 1. Calculate minimal size required to
  949. ;    successful subsequent allocation of a chunk.
  950. ; 2. Set maximum of it and malloc_state.segment_size as the new size.
  951. ; 3. If footprint limit is set and the selected size would overflow it,
  952. ;    decrease to the maximum allowed by the limit.
  953. ; 4. If the selected size is less than the minimal size, fail.
  954. ; 5. Call the kernel. If failed, retry several times halving
  955. ;    the requested size until either allocation succeeds or
  956. ;    the minimal size is reached; in the former case, try one last time
  957. ;    requesting the minimal size. If failed, pass the fail to the caller.
  958. ; 6. If allocation succeeded, add the final size to malloc_state.segment_size
  959. ;    for subsequent allocations.
  960. proc sys_alloc
  961.         call    trim_top
  962.         mov     edx, esi
  963.         add     edx, SYS_ALLOC_PADDING + 0xFFF
  964.         jc      .fail
  965.         and     edx, not 0xFFF
  966. ; edx = minimal memory required
  967.         mov     ecx, [ebp+malloc_state.segment_size]
  968.         cmp     ecx, edx
  969.         ja      @f
  970.         mov     ecx, edx
  971. @@:
  972.         mov     ebx, [ebp+malloc_state.footprint_limit]
  973.         test    ebx, ebx
  974.         jz      @f
  975.         sub     ebx, [ebp+malloc_state.footprint]
  976.         cmp     ecx, ebx
  977.         jb      @f
  978.         mov     ecx, ebx
  979. @@:
  980.         cmp     ecx, edx
  981.         jb      .fail
  982. .retry:
  983.         mov     eax, 68
  984.         mov     ebx, 12
  985.         call    FS_SYSCALL_PTR
  986.         test    eax, eax
  987.         jnz     .ok
  988.         cmp     ecx, edx
  989.         jbe     .fail
  990.         shr     ecx, 1
  991.         cmp     ecx, edx
  992.         jae     .retry
  993.         mov     ecx, edx
  994.         jmp     .retry
  995. .fail:
  996.         mov     FS_ERRNO, ENOMEM
  997.         xor     eax, eax
  998.         ret
  999. .ok:
  1000.         add     [ebp+malloc_state.segment_size], ecx
  1001.         add     [ebp+malloc_state.footprint], ecx
  1002.         mov     ebx, [ebp+malloc_state.footprint]
  1003.         cmp     ebx, [ebp+malloc_state.max_footprint]
  1004.         jb      @f
  1005.         mov     [ebp+malloc_state.max_footprint], ebx
  1006. @@:
  1007.         push    esi
  1008.         add_segment     ; ebp, eax, ecx
  1009.         pop     esi
  1010.         mov     ecx, [ebp+malloc_state.topsize]
  1011.         sub     ecx, esi
  1012.         jbe     .fail
  1013.         mov     [ebp+malloc_state.topsize], ecx
  1014.         mov     eax, [ebp+malloc_state.top]
  1015.         add     [ebp+malloc_state.top], esi
  1016.         add     [ebp+malloc_state.topmax], esi
  1017.         lea     edx, [ecx+PINUSE_BIT]
  1018.         mov     [eax+esi+mchunk_head], edx
  1019.         lea     edx, [esi+PINUSE_BIT+CINUSE_BIT]
  1020.         mov     [eax+mchunk_head], edx
  1021.         mark_inuse_foot eax+esi
  1022.         ret
  1023. endp
  1024.  
  1025. ; -----------------------  system deallocation --------------------------
  1026.  
  1027. proc chunk_trim
  1028.         add     edx, 0xFFF
  1029.         and     edx, not 0xFFF
  1030.         and     esi, not 0xFFF
  1031.         sub     esi, edx
  1032.         jbe     .nothing
  1033.         segment_holding edx
  1034.         mov     ecx, [eax+malloc_segment.base]
  1035.         mov     eax, 68
  1036.         mov     ebx, 26
  1037.         sub     edx, ecx
  1038.         call    FS_SYSCALL_PTR
  1039. .nothing:
  1040.         ret
  1041. endp
  1042.  
  1043. proc trim_top
  1044.         mov     edx, [ebp+malloc_state.top]
  1045.         xor     edx, [ebp+malloc_state.topmax]
  1046.         test    edx, not 0xFFF
  1047.         jz      .nothing
  1048.         push    esi
  1049.         mov     edx, [ebp+malloc_state.top]
  1050.         mov     esi, [ebp+malloc_state.topmax]
  1051.         mov     [ebp+malloc_state.topmax], edx
  1052.         add     esi, 0xFFF
  1053.         call    chunk_trim
  1054.         pop     esi
  1055. .nothing:
  1056.         ret
  1057. endp
  1058.  
  1059. proc sys_trim
  1060.         call    trim_top
  1061.         push    edi
  1062.         lea     edi, [ebp+malloc_state.release_list-tchunk_release_fd]
  1063.         mov     eax, [ebp+malloc_state.release_list]
  1064.         push    edi
  1065. .release_list:
  1066.         cmp     eax, [esp]
  1067.         jz      .release_done
  1068.         mov     edi, eax
  1069.         mov     esi, [eax+mchunk_prev_foot]
  1070.         sub     eax, [eax+mchunk_prev_foot]
  1071.         lea     edx, [eax+sizeof.malloc_tree_chunk-malloc_chunk.data]
  1072.         lea     esi, [eax+esi+tchunk_release_fd]
  1073.         call    chunk_trim
  1074.         mov     eax, [edi+tchunk_release_fd]
  1075.         mov     [edi+tchunk_release_fd], edi
  1076.         mov     [edi+tchunk_release_bk], edi
  1077.         jmp     .release_list
  1078. .release_done:
  1079.         mov     [ebp+malloc_state.release_list+0], eax
  1080.         mov     [ebp+malloc_state.release_list+4], eax
  1081.         pop     edi edi
  1082.         mov     [ebp+malloc_state.release_checks], RELEASE_CHECK_RATE
  1083.         ret
  1084. endp
  1085.  
  1086. macro trim_if_should
  1087. {
  1088.         dec     [ebp+malloc_state.release_checks]
  1089.         jnz     @f
  1090.         call    sys_trim
  1091. @@:
  1092. }
  1093.  
  1094. ; ---------------------------- malloc ---------------------------
  1095.  
  1096. ; allocate a large request from the best fitting chunk in a treebin
  1097. ; if succeeded, unlock the heap and return
  1098. ; if failed, go ahead
  1099. ; in: ebp -> malloc_state, esi = nb
  1100. macro tmalloc_large_and_return
  1101. {
  1102. local .find_in_bin, .follow_right, .try_next_bin, .found_subtree, .found_match, .no_new_chunk, .follow_left, .nothing
  1103.         push    edi
  1104. macro ret \{
  1105.         pop     edi
  1106.         ret
  1107. \}
  1108.         push    0
  1109.         push    0
  1110.         mov     eax, esi
  1111.         compute_tree_index eax
  1112. ; ecx = idx, eax = sizebits
  1113.         sub     [esp], esi
  1114. ; edx = rsize
  1115.         cmp     [ebp+malloc_state.treebins+ecx*4], 0
  1116.         jz      .try_next_bin
  1117. ; Traverse tree for this bin looking for node with size == nb
  1118.         mov     edi, [ebp+malloc_state.treebins+ecx*4]
  1119.         xor     ebx, ebx        ; The deepest untaken right subtree
  1120. .find_in_bin:
  1121.         mov     edx, [edi+mchunk_head]
  1122.         and     edx, not FLAG_BITS
  1123.         sub     edx, esi
  1124.         cmp     [esp], edx
  1125.         jbe     @f
  1126.         mov     [esp], edx
  1127.         mov     [esp+4], edi
  1128.         test    edx, edx
  1129.         jz      .found_match
  1130. @@:
  1131.         add     eax, eax
  1132.         jc      .follow_right
  1133.         cmp     dword [edi+tchunk_right_child], 0
  1134.         jz      @f
  1135.         mov     ebx, [edi+tchunk_right_child]
  1136. @@:
  1137.         cmp     dword [edi+tchunk_left_child], 0
  1138.         mov     edi, [edi+tchunk_left_child]
  1139.         jnz     .find_in_bin
  1140.         jmp     @f
  1141. .follow_right:
  1142.         cmp     dword [edi+tchunk_right_child], 0
  1143.         mov     edi, [edi+tchunk_right_child]
  1144.         jnz     .find_in_bin
  1145. @@:
  1146.         mov     edi, ebx        ; set t to least subtree holding sizes > nb
  1147.         test    ebx, ebx
  1148.         jnz     .found_subtree
  1149.         cmp     dword [esp+4], 0
  1150.         jnz     .found_match
  1151. .try_next_bin:
  1152. ; set t to root of next non-empty treebin
  1153.         mov     eax, [ebp+malloc_state.treemap]
  1154.         shr     eax, cl
  1155.         shr     eax, 1
  1156.         jz      .nothing
  1157.         bsf     eax, eax
  1158.         add     eax, ecx
  1159.         mov     edi, [ebp+malloc_state.treebins+(eax+1)*4]
  1160. .found_subtree:
  1161. ; find smallest of tree or subtree
  1162.         mov     edx, [edi+mchunk_head]
  1163.         and     edx, not FLAG_BITS
  1164.         sub     edx, esi
  1165.         cmp     [esp], edx
  1166.         jbe     @f
  1167.         mov     [esp], edx
  1168.         mov     [esp+4], edi
  1169. @@:
  1170.         cmp     dword [edi+tchunk_left_child], 0
  1171.         jnz     .follow_left
  1172.         cmp     dword [edi+tchunk_right_child], 0
  1173.         mov     edi, [edi+tchunk_right_child]
  1174.         jnz     .found_subtree
  1175.         cmp     dword [esp+4], 0
  1176.         jz      .nothing
  1177. .found_match:
  1178. ; If dv is a better fit, return 0 so malloc will use it
  1179.         mov     eax, [ebp+malloc_state.dvsize]
  1180.         sub     eax, esi
  1181.         cmp     [esp], eax
  1182.         jae     .nothing
  1183.         mov     eax, [esp+4]
  1184.         cmp     dword [esp], NSMALLBINS shl SMALLBIN_SHIFT
  1185.         jae     @f
  1186.         mov     ecx, [esp]
  1187.         add     ecx, esi
  1188.         add     ecx, eax
  1189.         mov     ebx, [ecx+tchunk_release_fd]
  1190.         mov     edx, [ecx+tchunk_release_bk]
  1191.         cmp     [ebx+tchunk_release_bk], ecx
  1192.         jnz     heap_corrupted
  1193.         cmp     [edx+tchunk_release_fd], ecx
  1194.         jnz     heap_corrupted
  1195.         mov     [ebx+tchunk_release_bk], edx
  1196.         mov     [edx+tchunk_release_fd], ebx
  1197. @@:
  1198.         mov     ecx, esi
  1199.         unlink_large_chunk      ; ebp, eax
  1200.         cmp     dword [esp], MIN_CHUNK_SIZE
  1201.         jb      .no_new_chunk
  1202.         lea     edx, [ecx+PINUSE_BIT+CINUSE_BIT]
  1203.         mov     [eax+mchunk_head], edx
  1204.         mark_inuse_foot eax+ecx
  1205.         lea     esi, [eax+ecx]
  1206.         mov     edx, [esp]
  1207.         lea     ecx, [edx+PINUSE_BIT]
  1208.         mov     [esi+mchunk_head], ecx
  1209.         mov     [esi+edx+mchunk_prev_foot], edx
  1210.         add     esp, 8
  1211. macro unlock_ret \{
  1212.         unlock_heap
  1213.         ret
  1214. \}
  1215.         insert_chunk unlock_ret ; ebp, esi, edx
  1216. purge unlock_ret
  1217. .no_new_chunk:
  1218.         add     ecx, [esp]
  1219.         lea     edx, [ecx+PINUSE_BIT+CINUSE_BIT]
  1220.         mov     [eax+mchunk_head], edx
  1221.         or      dword [eax+ecx+mchunk_head], PINUSE_BIT
  1222.         mark_inuse_foot eax+ecx
  1223.         add     esp, 8
  1224.         unlock_heap
  1225.         ret
  1226. .follow_left:
  1227.         mov     edi, [edi+tchunk_left_child]
  1228.         jmp     .found_subtree
  1229. .nothing:
  1230.         add     esp, 8
  1231.         pop     edi
  1232. purge ret
  1233. }
  1234.  
  1235. ; allocate a small request from the best fitting chunk in a treebin
  1236. ; in: ebp -> malloc_state, esi = size
  1237. macro tmalloc_small_and_return
  1238. {
  1239. local .follow_left, .found_best, .no_new_chunk
  1240.         bsf     ecx, [ebp+malloc_state.treemap]
  1241.         mov     eax, [ebp+malloc_state.treebins+ecx*4]
  1242.         mov     edx, eax
  1243.         mov     ecx, [eax+mchunk_head]
  1244.         and     ecx, not FLAG_BITS
  1245.         sub     ecx, esi
  1246. @@:
  1247.         cmp     dword [edx+tchunk_left_child], 0
  1248.         jnz     .follow_left
  1249.         cmp     dword [edx+tchunk_right_child], 0
  1250.         jz      .found_best
  1251.         mov     edx, [edx+tchunk_right_child]
  1252.         mov     ebx, [edx+mchunk_head]
  1253.         and     ebx, not FLAG_BITS
  1254.         sub     ebx, esi
  1255.         cmp     ecx, ebx
  1256.         jbe     @b
  1257.         mov     eax, edx
  1258.         mov     ecx, ebx
  1259.         jmp     @b
  1260. .follow_left:
  1261.         mov     edx, [edx+tchunk_left_child]
  1262.         mov     ebx, [edx+mchunk_head]
  1263.         and     ebx, not FLAG_BITS
  1264.         sub     ebx, esi
  1265.         cmp     ecx, ebx
  1266.         jbe     @b
  1267.         mov     eax, edx
  1268.         mov     ecx, ebx
  1269.         jmp     @b
  1270. .found_best:
  1271.         push    esi
  1272.         cmp     ecx, NSMALLBINS shl SMALLBIN_SHIFT
  1273.         jae     @f
  1274.         add     esi, ecx
  1275.         add     esi, eax
  1276.         mov     ebx, [esi+tchunk_release_fd]
  1277.         mov     edx, [esi+tchunk_release_bk]
  1278.         cmp     [ebx+tchunk_release_bk], esi
  1279.         jnz     heap_corrupted
  1280.         cmp     [edx+tchunk_release_fd], esi
  1281.         jnz     heap_corrupted
  1282.         mov     [ebx+tchunk_release_bk], edx
  1283.         mov     [edx+tchunk_release_fd], ebx
  1284. @@:
  1285.         unlink_large_chunk      ; ebp, eax
  1286.         pop     esi
  1287.         cmp     ecx, MIN_CHUNK_SIZE
  1288.         jb      .no_new_chunk
  1289.         lea     edx, [eax+esi]
  1290.         lea     ebx, [esi+PINUSE_BIT+CINUSE_BIT]
  1291.         mov     [eax+mchunk_head], ebx
  1292.         mark_inuse_foot edx
  1293.         lea     ebx, [ecx+PINUSE_BIT]
  1294.         mov     [edx+mchunk_head], ebx
  1295.         mov     [edx+ecx+mchunk_prev_foot], ecx
  1296.         replace_dv      ; ebp, ecx, edx
  1297.         unlock_heap
  1298.         ret
  1299. .no_new_chunk:
  1300.         lea     edx, [ecx+esi+PINUSE_BIT+CINUSE_BIT]
  1301.         add     ecx, esi
  1302.         mov     [eax+mchunk_head], edx
  1303.         or      dword [eax+ecx+mchunk_head], PINUSE_BIT
  1304.         mark_inuse_foot eax+ecx
  1305.         unlock_heap
  1306.         ret
  1307. }
  1308.  
  1309. ; in: ebp -> malloc_state
  1310. ; in: [bytes] = stack var with number of bytes to allocate
  1311. ; out: eax -> allocated data
  1312. macro do_malloc
  1313. {
  1314. ;
  1315. ;     Basic algorithm:
  1316. ;     If a small request (< 256 bytes minus per-chunk overhead):
  1317. ;       1. If one exists, use a remainderless chunk in associated smallbin.
  1318. ;          (Remainderless means that there are too few excess bytes to
  1319. ;          represent as a chunk.)
  1320. ;       2. If it is big enough, use the dv chunk, which is normally the
  1321. ;          chunk adjacent to the one used for the most recent small request.
  1322. ;       3. If one exists, split the smallest available chunk in a bin,
  1323. ;          saving remainder in dv.
  1324. ;       4. If it is big enough, use the top chunk.
  1325. ;       5. If available, get memory from system and use it
  1326. ;     Otherwise, for a large request:
  1327. ;       1. Find the smallest available binned chunk that fits, and use it
  1328. ;          if it is better fitting than dv chunk, splitting if necessary.
  1329. ;       2. If better fitting than any binned chunk, use the dv chunk.
  1330. ;       3. If request size >= mmap threshold, try to directly mmap this chunk.
  1331. ;       4. If it is big enough, use the top chunk.
  1332. ;       5. If available, get memory from system and use it
  1333. ;
  1334.         lock_heap
  1335.         mov     eax, [bytes]
  1336.         cmp     [bytes], MAX_SMALL_REQUEST
  1337.         ja      .large
  1338.         mov     ecx, MIN_CHUNK_SIZE
  1339.         cmp     eax, MIN_REQUEST
  1340.         jb      @f
  1341.         lea     ecx, [eax + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK]
  1342.         and     ecx, not CHUNK_ALIGN_MASK
  1343. @@:
  1344.         mov     esi, ecx
  1345.         shr     ecx, SMALLBIN_SHIFT
  1346.         mov     eax, [ebp + malloc_state.smallmap]
  1347.         shr     eax, cl
  1348.         test    eax, 3
  1349.         jz      .small.remainder
  1350. ; Remainderless fit to a smallbin.
  1351.         shr     eax, 1
  1352.         sbb     ecx, -1         ; Uses next bin if idx empty
  1353.         lea     edx, [ebp + malloc_state.smallbins + ecx*8]
  1354.         mov     eax, [ebp + malloc_state.smallbins + ecx*8 + mchunk_fd]
  1355.         unlink_first_small_chunk        ; ebp, edx, eax, ecx
  1356.         lea     edx, [ecx*SMALLBIN_WIDTH+PINUSE_BIT+CINUSE_BIT]
  1357.         mov     [eax+mchunk_head], edx
  1358.         or      dword [eax+ecx*SMALLBIN_WIDTH+mchunk_head], PINUSE_BIT
  1359.         mark_inuse_foot eax+ecx*SMALLBIN_WIDTH
  1360.         unlock_heap
  1361.         ret
  1362. .small.remainder:
  1363.         cmp     esi, [ebp+malloc_state.dvsize]
  1364.         jbe     .use_dv_chunk
  1365.         test    eax, eax
  1366.         jz      .small.try_split_large
  1367.         bsf     eax, eax
  1368.         add     ecx, eax
  1369.         lea     edx, [ebp + malloc_state.smallbins + ecx*8]
  1370.         mov     eax, [ebp + malloc_state.smallbins + ecx*8 + mchunk_fd]
  1371.         unlink_first_small_chunk        ; ebp, edx, eax, ecx
  1372.         lea     edx, [esi+PINUSE_BIT+CINUSE_BIT]
  1373.         mov     [eax+mchunk_head], edx
  1374.         lea     edx, [eax+esi]
  1375.         shl     ecx, SMALLBIN_SHIFT
  1376.         sub     ecx, esi
  1377.         mark_inuse_foot edx
  1378.         lea     ebx, [ecx+PINUSE_BIT]
  1379.         mov     [edx+mchunk_head], ebx
  1380.         mov     [edx+ecx+mchunk_prev_foot], ecx
  1381.         replace_dv      ; ebp, ecx, edx
  1382.         unlock_heap
  1383.         ret
  1384. .use_dv_chunk:
  1385.         mov     ecx, [ebp+malloc_state.dvsize]
  1386.         mov     eax, [ebp+malloc_state.dv]
  1387.         sub     ecx, esi
  1388.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  1389.         jb      @f
  1390.         cmp     ecx, NSMALLBINS shl SMALLBIN_SHIFT
  1391.         jae     @f
  1392.         lea     edx, [eax+esi]
  1393.         add     edx, ecx
  1394.         mov     ebx, [edx+tchunk_release_fd]
  1395.         cmp     [ebx+tchunk_release_bk], edx
  1396.         jnz     heap_corrupted
  1397.         mov     ebx, [edx+tchunk_release_bk]
  1398.         cmp     [ebx+tchunk_release_fd], edx
  1399.         jnz     heap_corrupted
  1400.         mov     edx, [edx+tchunk_release_fd]
  1401.         mov     [ebx+tchunk_release_fd], edx
  1402.         mov     [edx+tchunk_release_bk], ebx
  1403. @@:
  1404.         cmp     ecx, MIN_CHUNK_SIZE
  1405.         jb      .no_new_chunk_dv
  1406.         lea     edx, [eax+esi]
  1407.         mov     [ebp+malloc_state.dv], edx
  1408.         mov     [ebp+malloc_state.dvsize], ecx
  1409.         lea     ebx, [ecx+PINUSE_BIT]
  1410.         mov     [edx+mchunk_head], ebx
  1411.         mov     [edx+ecx+mchunk_prev_foot], ecx
  1412.         lea     ebx, [esi+PINUSE_BIT+CINUSE_BIT]
  1413.         mov     [eax+mchunk_head], ebx
  1414.         mark_inuse_foot edx
  1415.         unlock_heap
  1416.         ret
  1417. .no_new_chunk_dv:
  1418.         add     ecx, esi
  1419.         mov     [ebp+malloc_state.dv], 0
  1420.         mov     [ebp+malloc_state.dvsize], 0
  1421.         lea     ebx, [ecx+PINUSE_BIT+CINUSE_BIT]
  1422.         mov     [eax+mchunk_head], ebx
  1423.         or      dword [eax+ecx+mchunk_head], PINUSE_BIT
  1424.         mark_inuse_foot eax+ecx
  1425.         unlock_heap
  1426.         ret
  1427. .small.try_split_large:
  1428.         cmp     [ebp+malloc_state.treemap], 0
  1429.         jz      .from_top_or_sys
  1430.         tmalloc_small_and_return
  1431. .large:
  1432.         cmp     eax, MAX_REQUEST
  1433.         jae     .fail
  1434.         lea     esi, [eax + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK]
  1435.         and     esi, not CHUNK_ALIGN_MASK
  1436.         cmp     [ebp+malloc_state.treemap], 0
  1437.         jz      .from_dv_top_or_sys
  1438.         tmalloc_large_and_return        ; can fail
  1439. .from_dv_top_or_sys:
  1440.         cmp     esi, [ebp+malloc_state.dvsize]
  1441.         jbe     .use_dv_chunk
  1442. .from_top_or_sys:
  1443. ; Directly map large chunks
  1444.         cmp     esi, [ebp+malloc_state.mmap_threshold]
  1445.         jb      @f
  1446.         mov     ecx, esi
  1447.         call    mmap_alloc
  1448.         test    eax, eax
  1449.         jz      @f
  1450.         unlock_heap
  1451.         ret
  1452. @@:
  1453.         cmp     esi, [ebp+malloc_state.topsize]
  1454.         jae     .from_sys
  1455.         mov     eax, [ebp+malloc_state.top]
  1456.         mov     ecx, [ebp+malloc_state.topsize]
  1457.         lea     edx, [eax+esi]
  1458.         sub     ecx, esi
  1459.         mov     [ebp+malloc_state.top], edx
  1460.         cmp     edx, [ebp+malloc_state.topmax]
  1461.         jb      @f
  1462.         mov     [ebp+malloc_state.topmax], edx
  1463. @@:
  1464.         mov     [ebp+malloc_state.topsize], ecx
  1465.         lea     ebx, [ecx+PINUSE_BIT]
  1466.         mov     [edx+mchunk_head], ebx
  1467.         lea     ebx, [esi+PINUSE_BIT+CINUSE_BIT]
  1468.         mov     [eax+mchunk_head], ebx
  1469.         mark_inuse_foot edx
  1470.         unlock_heap
  1471.         ret
  1472. .from_sys:
  1473.         call    sys_alloc
  1474.         unlock_heap
  1475.         ret
  1476. .fail:
  1477.         mov     FS_ERRNO, ENOMEM
  1478.         xor     eax, eax
  1479.         unlock_heap
  1480.         ret
  1481. }
  1482.  
  1483. ; ---------------------------- free ---------------------------
  1484.  
  1485. ; in: ebp -> malloc_state
  1486. ; in: [mem] = stack var with pointer to free
  1487. macro do_free
  1488. {
  1489. ;     Consolidate freed chunks with preceeding or succeeding bordering
  1490. ;     free chunks, if they exist, and then place in a bin.  Intermixed
  1491. ;     with special cases for top, dv, mmapped chunks, and usage errors.
  1492.         cmp     [mem], 0
  1493.         jz      .nothing
  1494. if FOOTERS
  1495.         mov     ecx, [mem]
  1496.         mov     eax, [ecx+mchunk_head]
  1497.         and     eax, not FLAG_BITS
  1498.         mov     eax, [ecx+eax+mchunk_prev_foot]
  1499.         xor     eax, [malloc_magic]
  1500.         cmp     eax, ebp
  1501.         jnz     heap_corrupted
  1502. end if
  1503.         lock_heap
  1504.         mov     eax, [mem]
  1505.         mov     ecx, [eax+mchunk_head]
  1506.         mov     edx, ecx
  1507.         and     ecx, INUSE_BITS
  1508. assert PINUSE_BIT = 1
  1509. assert CINUSE_BIT = 2
  1510. ; Possible values of ecx:
  1511. ; 0 = mmapped chunk, should be rare
  1512. ; 1 = illegal, trying to double-free
  1513. ; 2 = previous chunk is not in use, merge backwards
  1514. ; 3 = previous chunk is in use, no merge backwards
  1515.         and     edx, not FLAG_BITS
  1516.         cmp     ecx, 2
  1517.         ja      .see_forward
  1518.         jb      .free_mmapped
  1519. ; turn CINUSE_BIT to PINUSE_BIT, increase chances to detect double-free
  1520.         dec     dword [eax+mchunk_head]
  1521.         cmp     dword [eax+mchunk_prev_foot], NSMALLBINS shl SMALLBIN_SHIFT
  1522.         jb      @f
  1523.         mov     ebx, [eax+tchunk_release_fd]
  1524.         mov     ecx, [eax+tchunk_release_bk]
  1525.         cmp     [ebx+tchunk_release_bk], eax
  1526.         jnz     heap_corrupted
  1527.         cmp     [ecx+tchunk_release_fd], eax
  1528.         jnz     heap_corrupted
  1529.         mov     [ebx+tchunk_release_bk], ecx
  1530.         mov     [ecx+tchunk_release_fd], ebx
  1531. @@:
  1532.         mov     ecx, [eax+mchunk_prev_foot]
  1533.         add     edx, [eax+mchunk_prev_foot]
  1534.         sub     eax, [eax+mchunk_prev_foot]
  1535.         cmp     eax, [ebp+malloc_state.dv]
  1536.         jz      .append_dv
  1537.         push    edx
  1538.         mov     edx, ecx
  1539.         unlink_chunk    ; ebp, eax, edx
  1540.         pop     edx
  1541. .see_forward:
  1542.         mov     esi, eax
  1543. assert PINUSE_BIT = 1
  1544.         btr     dword [eax+edx+mchunk_head], 0
  1545.         jnc     heap_corrupted
  1546.         test    dword [eax+edx+mchunk_head], CINUSE_BIT
  1547.         jnz     .consolidated
  1548. .consolidate_forward:
  1549.         add     eax, edx
  1550.         cmp     eax, [ebp+malloc_state.top]
  1551.         jz      .prepend_top
  1552.         cmp     eax, [ebp+malloc_state.dv]
  1553.         jz      .prepend_dv
  1554.         push    esi edx
  1555.         mov     edx, [eax+mchunk_head]
  1556.         and     edx, not FLAG_BITS
  1557.         add     [esp], edx
  1558.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1559.         jae     .consolidate_large
  1560.         unlink_small_chunk      ; ebp, eax, edx
  1561.         jmp     .consolidate_common
  1562. .consolidate_large:
  1563.         lea     ecx, [eax+edx]
  1564.         mov     ebx, [eax+edx+tchunk_release_fd]
  1565.         mov     edx, [eax+edx+tchunk_release_bk]
  1566.         cmp     [ebx+tchunk_release_bk], ecx
  1567.         jnz     heap_corrupted
  1568.         cmp     [edx+tchunk_release_fd], ecx
  1569.         jnz     heap_corrupted
  1570.         mov     [ebx+tchunk_release_bk], edx
  1571.         mov     [edx+tchunk_release_fd], ebx
  1572.         unlink_large_chunk      ; ebp, eax
  1573. .consolidate_common:
  1574.         pop     edx esi
  1575.         cmp     esi, [ebp+malloc_state.dv]
  1576.         jz      .dv_consolidated
  1577. .consolidated:
  1578.         lea     ecx, [edx+PINUSE_BIT]
  1579.         mov     [esi+mchunk_head], ecx
  1580.         mov     [esi+edx+mchunk_prev_foot], edx
  1581.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1582.         jae     .large
  1583.         insert_small_chunk      ; ebp, esi, edx
  1584.         unlock_heap
  1585. .nothing:
  1586.         ret
  1587. .large:
  1588.         lea     ecx, [esi+edx]
  1589.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1590.         mov     ebx, [ebp+malloc_state.release_list]
  1591.         cmp     [ebx+tchunk_release_bk], eax
  1592.         jnz     heap_corrupted
  1593.         mov     [ecx+tchunk_release_fd], ebx
  1594.         mov     [ecx+tchunk_release_bk], eax
  1595.         mov     [ebx+tchunk_release_bk], ecx
  1596.         mov     [eax+tchunk_release_fd], ecx
  1597. @@:
  1598.         push    edi
  1599. macro trim_ret \{
  1600.         trim_if_should
  1601.         unlock_heap
  1602.         pop     edi
  1603.         ret
  1604. \}
  1605.         insert_large_chunk trim_ret     ; ebp, esi, edx
  1606. purge trim_ret
  1607. .dv_consolidated:
  1608.         mov     [esi+edx+mchunk_prev_foot], edx
  1609.         mov     [ebp+malloc_state.dvsize], edx
  1610.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1611.         jb      @f
  1612.         lea     ecx, [esi+edx]
  1613.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1614.         mov     ebx, [ebp+malloc_state.release_list]
  1615.         cmp     [ebx+tchunk_release_bk], eax
  1616.         jnz     heap_corrupted
  1617.         mov     [ecx+tchunk_release_fd], ebx
  1618.         mov     [ecx+tchunk_release_bk], eax
  1619.         mov     [ebx+tchunk_release_bk], ecx
  1620.         mov     [eax+tchunk_release_fd], ecx
  1621. @@:
  1622. assert PINUSE_BIT = 1
  1623.         inc     edx
  1624.         mov     [esi+mchunk_head], edx
  1625.         unlock_heap
  1626.         ret
  1627. .append_dv:
  1628.         mov     esi, eax
  1629. assert PINUSE_BIT = 1
  1630.         btr     dword [eax+edx+mchunk_head], 0
  1631.         jnc     heap_corrupted
  1632.         test    dword [eax+edx+mchunk_head], CINUSE_BIT
  1633.         jz      .consolidate_forward
  1634.         mov     [ebp+malloc_state.dvsize], edx
  1635.         lea     ecx, [edx+PINUSE_BIT]
  1636.         mov     [eax+mchunk_head], ecx
  1637.         mov     [eax+edx+mchunk_prev_foot], edx
  1638.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1639.         jb      @f
  1640.         add     edx, eax
  1641.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1642.         mov     ebx, [ebp+malloc_state.release_list]
  1643.         cmp     [ebx+tchunk_release_bk], eax
  1644.         jnz     heap_corrupted
  1645.         mov     [edx+tchunk_release_fd], ebx
  1646.         mov     [edx+tchunk_release_bk], eax
  1647.         mov     [ebx+tchunk_release_bk], edx
  1648.         mov     [eax+tchunk_release_fd], edx
  1649. @@:
  1650.         unlock_heap
  1651.         ret
  1652. .prepend_dv:
  1653.         add     edx, [ebp+malloc_state.dvsize]
  1654.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  1655.         jb      @f
  1656.         lea     ecx, [esi+edx]
  1657.         mov     eax, [esi+edx+tchunk_release_fd]
  1658.         mov     ebx, [esi+edx+tchunk_release_bk]
  1659.         cmp     [eax+tchunk_release_bk], ecx
  1660.         jnz     heap_corrupted
  1661.         cmp     [ebx+tchunk_release_fd], ecx
  1662.         jnz     heap_corrupted
  1663.         mov     [eax+tchunk_release_bk], ebx
  1664.         mov     [ebx+tchunk_release_fd], eax
  1665. @@:
  1666.         mov     [ebp+malloc_state.dvsize], edx
  1667.         mov     [ebp+malloc_state.dv], esi
  1668.         mov     [esi+edx+mchunk_prev_foot], edx
  1669.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1670.         jb      @f
  1671.         lea     ecx, [esi+edx]
  1672.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1673.         mov     ebx, [ebp+malloc_state.release_list]
  1674.         cmp     [ebx+tchunk_release_bk], eax
  1675.         jnz     heap_corrupted
  1676.         mov     [ecx+tchunk_release_fd], ebx
  1677.         mov     [ecx+tchunk_release_bk], eax
  1678.         mov     [ebx+tchunk_release_bk], ecx
  1679.         mov     [eax+tchunk_release_fd], ecx
  1680. @@:
  1681. assert PINUSE_BIT = 1
  1682.         inc     edx
  1683.         mov     [esi+mchunk_head], edx
  1684.         unlock_heap
  1685.         ret
  1686. .prepend_top:
  1687.         add     edx, [ebp+malloc_state.topsize]
  1688.         mov     [ebp+malloc_state.topsize], edx
  1689.         mov     [ebp+malloc_state.top], esi
  1690. assert PINUSE_BIT = 1
  1691.         inc     edx
  1692.         mov     [esi+mchunk_head], edx
  1693.         cmp     esi, [ebp+malloc_state.dv]
  1694.         jnz     @f
  1695.         mov     [ebp+malloc_state.dv], 0
  1696.         mov     [ebp+malloc_state.dvsize], 0
  1697. @@:
  1698.         trim_if_should
  1699.         unlock_heap
  1700.         ret
  1701. .free_mmapped:
  1702.         dec     ecx
  1703.         jz      heap_corrupted
  1704.         mov     ecx, eax
  1705.         add     edx, [eax+mchunk_prev_foot]
  1706.         add     edx, MMAP_FOOT_PAD-8
  1707.         test    edx, 0xFFF
  1708.         jnz     heap_corrupted
  1709.         sub     [ebp+malloc_state.footprint], edx
  1710.         sub     ecx, [ecx+mchunk_prev_foot]
  1711.         test    ecx, 0xFFF
  1712.         jnz     heap_corrupted
  1713.         mov     eax, [ecx]
  1714.         mov     ebx, [ecx+4]
  1715.         cmp     [eax+4], ecx
  1716.         jnz     heap_corrupted
  1717.         cmp     [ebx], ecx
  1718.         jnz     heap_corrupted
  1719.         mov     [eax+4], ebx
  1720.         mov     [ebx], eax
  1721.         mov     eax, 68
  1722.         mov     ebx, 13
  1723.         call    FS_SYSCALL_PTR
  1724.         unlock_heap
  1725.         ret
  1726. }
  1727.  
  1728. ; in: ebp -> malloc_state
  1729. ; in: [n_elements] = stack var with number of elements
  1730. ; in: [elem_size] = stack var with element size
  1731. macro do_calloc malloc_call
  1732. {
  1733.         mov     eax, [n_elements]
  1734.         mul     [elem_size]
  1735.         test    edx, edx
  1736.         jnz     .fail
  1737.         mov     [n_elements], eax
  1738.         malloc_call
  1739.         test    eax, eax
  1740.         jz      .nothing
  1741.         test    dword [eax+mchunk_head], INUSE_BITS
  1742.         jz      .nothing
  1743.         push    eax edi
  1744.         mov     edi, eax
  1745.         mov     ecx, [n_elements]
  1746.         add     ecx, 3
  1747.         shr     ecx, 2
  1748.         xor     eax, eax
  1749.         rep stosd
  1750.         pop     edi eax
  1751. .nothing:
  1752.         ret
  1753. .fail:
  1754.         mov     FS_ERRNO, ENOMEM
  1755.         xor     eax, eax
  1756.         ret
  1757. }
  1758.  
  1759. ; ------------ Internal support for realloc, memalign, etc --------------
  1760. ; Try to realloc; only in-place unless can_move true
  1761. ; in: ebp -> malloc_state
  1762. ; in: [oldmem] = stack var with pointer to realloc
  1763. ; in: [bytes] = stack var with number of bytes to allocate
  1764. macro try_realloc_chunk can_move
  1765. {
  1766.         lock_heap
  1767.         mov     eax, [oldmem]
  1768.         mov     ecx, MIN_CHUNK_SIZE
  1769.         cmp     [bytes], MIN_REQUEST
  1770.         jb      @f
  1771.         mov     ecx, [bytes]
  1772.         add     ecx, CHUNK_OVERHEAD + CHUNK_ALIGN_MASK
  1773.         and     ecx, not CHUNK_ALIGN_MASK
  1774. @@:
  1775.         mov     [bytes], ecx
  1776.         mov     edx, [eax+mchunk_head]
  1777.         and     edx, not FLAG_BITS
  1778. ; Possible values of [eax+mchunk_head] and INUSE_BIT:
  1779. ; 0 = mmapped chunk, should be rare
  1780. ; 1 = illegal, trying to realloc already-freed chunk
  1781. ; 2,3 = normal chunk
  1782.         test    dword [eax+mchunk_head], CINUSE_BIT
  1783.         jz      .mmapped
  1784.         test    dword [eax+edx+mchunk_head], PINUSE_BIT
  1785.         jz      heap_corrupted
  1786.         cmp     ecx, edx
  1787.         jbe     .realloc_decrease
  1788.         add     eax, edx
  1789.         cmp     eax, [ebp+malloc_state.top]
  1790.         jz      .move_top
  1791.         cmp     eax, [ebp+malloc_state.dv]
  1792.         jz      .extend_into_dv
  1793.         test    dword [eax+mchunk_head], CINUSE_BIT
  1794.         jnz     .failed
  1795. ; extend into next free chunk
  1796.         push    edx
  1797.         mov     edx, [eax+mchunk_head]
  1798.         and     edx, not FLAG_BITS
  1799.         add     [esp], edx
  1800.         sub     [esp], ecx
  1801.         jb      .failed_pop
  1802.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1803.         jae     .large
  1804.         unlink_small_chunk      ; ebp, eax, edx
  1805.         jmp     .common
  1806. .large:
  1807.         cmp     dword [esp], NSMALLBINS shl SMALLBIN_SHIFT
  1808.         jae     @f
  1809.         lea     ecx, [eax+edx]
  1810.         mov     ebx, [eax+edx+tchunk_release_fd]
  1811.         mov     edx, [eax+edx+tchunk_release_bk]
  1812.         cmp     [ebx+tchunk_release_bk], ecx
  1813.         jnz     heap_corrupted
  1814.         cmp     [edx+tchunk_release_fd], ecx
  1815.         jnz     heap_corrupted
  1816.         mov     [ebx+tchunk_release_bk], edx
  1817.         mov     [edx+tchunk_release_fd], ebx
  1818. @@:
  1819.         unlink_large_chunk      ; ebp, eax
  1820. .common:
  1821.         pop     edx
  1822.         mov     eax, [oldmem]
  1823.         mov     ecx, [bytes]
  1824.         cmp     edx, MIN_CHUNK_SIZE
  1825.         jae     .add_chunk
  1826. .no_new_chunk:
  1827.         add     edx, ecx
  1828.         mov     ebx, [eax+mchunk_head]
  1829.         and     ebx, PINUSE_BIT
  1830.         lea     ebx, [edx+ebx+CINUSE_BIT]
  1831.         mov     [eax+mchunk_head], ebx
  1832.         or      dword [eax+edx+mchunk_head], PINUSE_BIT
  1833.         mark_inuse_foot eax+edx
  1834. .nothing:
  1835.         unlock_heap
  1836.         ret
  1837. .realloc_decrease:
  1838.         test    dword [eax+edx+mchunk_head], CINUSE_BIT
  1839.         jz      .prepend_free
  1840.         sub     edx, ecx
  1841.         cmp     edx, MIN_CHUNK_SIZE
  1842.         jb      .nothing
  1843.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1844.         jb      .add_chunk
  1845.         lea     ebx, [eax+ecx]
  1846.         add     ebx, edx
  1847.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1848.         mov     esi, [ebp+malloc_state.release_list]
  1849.         cmp     [esi+tchunk_release_bk], eax
  1850.         jnz     heap_corrupted
  1851.         mov     [ebx+tchunk_release_fd], esi
  1852.         mov     [ebx+tchunk_release_bk], eax
  1853.         mov     [esi+tchunk_release_bk], ebx
  1854.         mov     [eax+tchunk_release_fd], ebx
  1855.         mov     eax, [oldmem]
  1856. .add_chunk:
  1857.         mov     ebx, [eax+mchunk_head]
  1858.         lea     esi, [eax+ecx]
  1859.         and     ebx, PINUSE_BIT
  1860.         lea     ebx, [ecx+ebx+CINUSE_BIT]
  1861.         mov     [eax+mchunk_head], ebx
  1862.         mark_inuse_foot esi
  1863.         lea     ecx, [edx+PINUSE_BIT]
  1864.         mov     [esi+mchunk_head], ecx
  1865.         mov     [esi+edx+mchunk_prev_foot], edx
  1866.         and     dword [esi+edx+mchunk_head], not PINUSE_BIT
  1867.         push    edi
  1868. macro unlock_ret \{
  1869.         pop     edi
  1870.         unlock_heap
  1871.         ret
  1872. \}
  1873.         insert_chunk unlock_ret ; ebp, esi, edx
  1874. purge unlock_ret
  1875. .prepend_free:
  1876.         add     eax, edx
  1877.         cmp     eax, [ebp+malloc_state.top]
  1878.         jz      .move_top
  1879.         cmp     eax, [ebp+malloc_state.dv]
  1880.         jz      .prepend_dv
  1881.         sub     edx, ecx
  1882.         push    edx
  1883.         mov     edx, [eax+mchunk_head]
  1884.         and     edx, not FLAG_BITS
  1885.         add     [esp], edx
  1886.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1887.         jae     .prepend_old_large
  1888.         unlink_small_chunk      ; ebp, eax, edx
  1889.         jmp     .prepend_old_common
  1890. .prepend_old_large:
  1891.         add     edx, eax
  1892.         mov     ebx, [edx+tchunk_release_fd]
  1893.         mov     ecx, [edx+tchunk_release_bk]
  1894.         cmp     [ebx+tchunk_release_bk], edx
  1895.         jnz     heap_corrupted
  1896.         cmp     [ecx+tchunk_release_fd], edx
  1897.         jnz     heap_corrupted
  1898.         mov     [ebx+tchunk_release_bk], ecx
  1899.         mov     [ecx+tchunk_release_fd], ebx
  1900.         unlink_large_chunk      ; ebp, eax
  1901. .prepend_old_common:
  1902.         pop     edx
  1903.         mov     esi, [oldmem]
  1904.         add     esi, [bytes]
  1905.         mov     [esi+edx+mchunk_prev_foot], edx
  1906.         lea     ecx, [edx+PINUSE_BIT]
  1907.         mov     [esi+mchunk_head], ecx
  1908.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1909.         jb      .prepend_new_small
  1910.         lea     ecx, [esi+edx]
  1911.         lea     eax, [ebp+malloc_state.release_list-tchunk_release_fd]
  1912.         mov     ebx, [ebp+malloc_state.release_list]
  1913.         cmp     [ebx+tchunk_release_bk], eax
  1914.         jnz     heap_corrupted
  1915.         mov     [eax+tchunk_release_fd], ecx
  1916.         mov     [ebx+tchunk_release_bk], ecx
  1917.         mov     [ecx+tchunk_release_fd], ebx
  1918.         mov     [ecx+tchunk_release_bk], eax
  1919.         push    edi
  1920. macro after_insert \{
  1921.         pop     edi
  1922.         jmp     .prepend_new_common
  1923. \}
  1924.         insert_large_chunk after_insert ; ebp, esi, edx
  1925. purge after_insert
  1926. .prepend_new_small:
  1927.         insert_small_chunk      ; ebp, esi, edx
  1928. .prepend_new_common:
  1929.         mov     eax, [oldmem]
  1930.         mov     ecx, [bytes]
  1931.         mark_inuse_foot eax+ecx
  1932.         mov     ebx, [eax+mchunk_head]
  1933.         and     ebx, PINUSE_BIT
  1934.         lea     ebx, [ebx+ecx+CINUSE_BIT]
  1935.         mov     [eax+mchunk_head], ebx
  1936.         unlock_heap
  1937.         ret
  1938. .prepend_dv:
  1939.         add     edx, [ebp+malloc_state.dvsize]
  1940.         add     eax, [ebp+malloc_state.dvsize]
  1941.         sub     edx, ecx
  1942.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1943.         jb      .move_dv
  1944.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  1945.         jb      @f
  1946.         cmp     [eax+tchunk_release_fd], eax
  1947.         jnz     .move_dv
  1948. @@:
  1949.         lea     ebx, [ebp+malloc_state.release_list-tchunk_release_fd]
  1950.         mov     esi, [ebp+malloc_state.release_list]
  1951.         cmp     [esi+tchunk_release_bk], ebx
  1952.         jnz     heap_corrupted
  1953.         mov     [eax+tchunk_release_fd], esi
  1954.         mov     [eax+tchunk_release_bk], ebx
  1955.         mov     [esi+tchunk_release_bk], eax
  1956.         mov     [ebx+tchunk_release_fd], eax
  1957.         jmp     .move_dv
  1958. .extend_into_dv:
  1959.         add     edx, [ebp+malloc_state.dvsize]
  1960.         sub     edx, ecx
  1961.         jb      .failed
  1962.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  1963.         jb      .move_dv
  1964.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  1965.         jae     .move_dv
  1966.         add     eax, [ebp+malloc_state.dvsize]
  1967.         mov     ebx, [eax+tchunk_release_fd]
  1968.         mov     esi, [eax+tchunk_release_bk]
  1969.         cmp     [ebx+tchunk_release_bk], eax
  1970.         jnz     heap_corrupted
  1971.         cmp     [esi+tchunk_release_fd], eax
  1972.         jnz     heap_corrupted
  1973.         mov     [ebx+tchunk_release_bk], esi
  1974.         mov     [esi+tchunk_release_fd], ebx
  1975. .move_dv:
  1976.         mov     eax, [oldmem]
  1977.         cmp     edx, MIN_CHUNK_SIZE
  1978.         jb      .dv_no_new_chunk
  1979.         mov     ebx, [eax+mchunk_head]
  1980.         and     ebx, PINUSE_BIT
  1981.         lea     ebx, [ecx+ebx+CINUSE_BIT]
  1982.         mov     [eax+mchunk_head], ebx
  1983.         add     ecx, eax
  1984.         mark_inuse_foot ecx
  1985.         lea     ebx, [edx+PINUSE_BIT]
  1986.         mov     [ecx+mchunk_head], ebx
  1987.         mov     [ecx+edx+mchunk_prev_foot], edx
  1988.         and     dword [ecx+edx+mchunk_head], not PINUSE_BIT
  1989.         mov     [ebp+malloc_state.dvsize], edx
  1990.         mov     [ebp+malloc_state.dv], ecx
  1991.         unlock_heap
  1992.         ret
  1993. .dv_no_new_chunk:
  1994.         add     edx, ecx
  1995.         mov     ebx, [eax+mchunk_head]
  1996.         and     ebx, PINUSE_BIT
  1997.         lea     ebx, [edx+ebx+CINUSE_BIT]
  1998.         mov     [eax+mchunk_head], ebx
  1999.         or      dword [eax+edx+mchunk_head], PINUSE_BIT
  2000.         mark_inuse_foot eax+edx
  2001.         mov     [ebp+malloc_state.dvsize], 0
  2002.         mov     [ebp+malloc_state.dv], 0
  2003.         unlock_heap
  2004.         ret
  2005. .move_top:
  2006.         add     edx, [ebp+malloc_state.topsize]
  2007.         sub     edx, ecx
  2008.         jbe     .failed
  2009.         mov     eax, [oldmem]
  2010.         mov     ebx, [eax+mchunk_head]
  2011.         and     ebx, PINUSE_BIT
  2012.         lea     ebx, [ecx+ebx+CINUSE_BIT]
  2013.         mov     [eax+mchunk_head], ebx
  2014.         add     ecx, eax
  2015.         mark_inuse_foot ecx
  2016.         mov     [ebp+malloc_state.top], ecx
  2017.         mov     [ebp+malloc_state.topsize], edx
  2018. assert PINUSE_BIT = 1
  2019.         inc     edx
  2020.         mov     [ecx+mchunk_head], edx
  2021.         unlock_heap
  2022.         ret
  2023. .mmapped:
  2024.         test    dword [eax+mchunk_head], PINUSE_BIT
  2025.         jnz     heap_corrupted
  2026.         mov     edx, eax
  2027. if can_move
  2028.         mov     ebx, 1
  2029. else
  2030.         xor     ebx, ebx
  2031. end if
  2032.         call    mmap_resize
  2033.         test    eax, eax
  2034.         jz      .failed
  2035.         unlock_heap
  2036.         ret
  2037. .failed_pop:
  2038.         pop     edx
  2039. .failed:
  2040.         unlock_heap
  2041. }
  2042.  
  2043. ; ------------------ Exported realloc, memalign, etc --------------------
  2044.  
  2045. ; in: ebp -> malloc_state
  2046. ; in: [oldmem] = stack var with pointer to realloc
  2047. ; in: [bytes] = stack var with number of bytes to allocate
  2048. macro do_realloc malloc_call, free_call
  2049. {
  2050.         cmp     [oldmem], 0
  2051.         jz      .malloc
  2052.         cmp     [bytes], 0
  2053.         jz      .free
  2054.         cmp     [bytes], MAX_REQUEST
  2055.         jae     .fail
  2056. if FOOTERS
  2057.         mov     ecx, [oldmem]
  2058.         mov     eax, [ecx+mchunk_head]
  2059.         and     eax, not FLAG_BITS
  2060.         mov     eax, [ecx+eax+mchunk_prev_foot]
  2061.         xor     eax, [malloc_magic]
  2062.         cmp     eax, ebp
  2063.         jnz     heap_corrupted
  2064. end if
  2065.         try_realloc_chunk 1     ; ebp, [oldmem], [bytes]
  2066.         sub     [bytes], CHUNK_OVERHEAD ; try_realloc_chunk has padded [bytes]
  2067.         malloc_call [bytes]
  2068.         test    eax, eax
  2069.         jz      .justret
  2070.         mov     esi, [oldmem]
  2071.         push    eax
  2072.         push    edi
  2073.         mov     ecx, [esi+mchunk_head]
  2074.         mov     edi, eax
  2075.         mov     edx, MMAP_CHUNK_OVERHEAD
  2076.         test    ecx, INUSE_BITS
  2077.         jz      @f
  2078.         mov     edx, CHUNK_OVERHEAD
  2079. @@:
  2080.         and     ecx, not FLAG_BITS
  2081.         sub     ecx, edx
  2082.         cmp     ecx, [bytes+8]
  2083.         jb      @f
  2084.         mov     ecx, [bytes+8]
  2085. @@:
  2086.         shr     ecx, 2
  2087.         rep movsd
  2088.         pop     edi
  2089.         free_call [oldmem+4]
  2090.         pop     eax
  2091. .justret:
  2092.         ret
  2093. .malloc:
  2094.         malloc_call [bytes]
  2095.         ret
  2096. .free:
  2097.         free_call [oldmem]
  2098.         xor     eax, eax
  2099.         ret
  2100. .fail:
  2101.         mov     FS_ERRNO, ENOMEM
  2102.         xor     eax, eax
  2103.         ret
  2104. }
  2105.  
  2106. ; in: ebp -> malloc_state
  2107. ; in: [oldmem] = stack var with pointer to realloc
  2108. ; in: [bytes] = stack var with number of bytes to allocate
  2109. macro do_realloc_in_place
  2110. {
  2111.         cmp     [oldmem], 0
  2112.         jz      .fail
  2113.         cmp     [bytes], MAX_REQUEST
  2114.         jae     .fail
  2115. if FOOTERS
  2116.         mov     ecx, [oldmem]
  2117.         mov     eax, [ecx+mchunk_head]
  2118.         and     eax, not FLAG_BITS
  2119.         mov     eax, [ecx+eax+mchunk_prev_foot]
  2120.         xor     eax, [malloc_magic]
  2121.         cmp     eax, ebp
  2122.         jnz     heap_corrupted
  2123. end if
  2124.         try_realloc_chunk 0     ; ebp, [oldmem], [bytes]
  2125. .fail:
  2126.         xor     eax, eax
  2127.         ret
  2128. }
  2129.  
  2130. ; in: ebp -> malloc_state
  2131. ; in: [alignment] = stack var with required alignment
  2132. ; in: [bytes] = stack var with number of bytes to allocate
  2133. macro do_memalign malloc_call
  2134. {
  2135.         mov     eax, [alignment]
  2136.         cmp     [alignment], MALLOC_ALIGNMENT
  2137.         jbe     .just_malloc
  2138.         lea     edx, [eax-1]
  2139.         cmp     eax, MIN_CHUNK_SIZE
  2140.         jb      .set_to_min_chunk_size
  2141.         test    eax, edx
  2142.         jnz     .set_align_pow2
  2143. .alignment_ok:
  2144.         add     eax, [bytes]
  2145.         jc      .too_large
  2146.         cmp     eax, MAX_REQUEST
  2147.         jae     .too_large
  2148.         mov     ecx, MIN_CHUNK_SIZE
  2149.         cmp     [bytes], MIN_REQUEST
  2150.         jb      @f
  2151.         mov     ecx, [bytes]
  2152.         add     ecx, CHUNK_OVERHEAD + CHUNK_ALIGN_MASK
  2153.         and     ecx, not CHUNK_ALIGN_MASK
  2154. @@:
  2155.         mov     [bytes], ecx
  2156.         add     ecx, [alignment]
  2157.         add     ecx, MIN_CHUNK_SIZE - CHUNK_OVERHEAD
  2158.         malloc_call ecx
  2159.         test    eax, eax
  2160.         jz      .nothing
  2161.         mov     esi, eax
  2162.         lock_heap
  2163.         mov     eax, esi
  2164.         mov     edx, [alignment]
  2165.         dec     edx
  2166.         test    esi, edx
  2167.         jz      .aligned
  2168. ; Find an aligned spot inside chunk.  Since we need to give
  2169. ; back leading space in a chunk of at least MIN_CHUNK_SIZE, if
  2170. ; the first calculation places us at a spot with less than
  2171. ; MIN_CHUNK_SIZE leader, we can move to the next aligned spot.
  2172. ; We've allocated enough total room so that this is always
  2173. ; possible.
  2174.         not     edx
  2175.         lea     eax, [esi-1]
  2176.         add     eax, [alignment]
  2177.         and     eax, edx
  2178.         mov     edx, eax
  2179.         sub     edx, esi
  2180.         cmp     edx, MIN_CHUNK_SIZE
  2181.         jae     @f
  2182.         add     eax, [alignment]
  2183.         add     edx, [alignment]
  2184. @@:
  2185.         test    dword [esi+mchunk_head], INUSE_BITS
  2186.         jz      .unaligned_mmapped
  2187. ; give back leader, use the rest
  2188.         mov     ecx, [esi+mchunk_head]
  2189.         and     ecx, not FLAG_BITS
  2190.         sub     ecx, edx
  2191.         mark_inuse_foot eax+ecx
  2192.         or      ecx, CINUSE_BIT
  2193.         mov     [eax+mchunk_head], ecx
  2194.         test    dword [esi+mchunk_head], PINUSE_BIT
  2195.         jnz     .insert_before
  2196.         mov     ebx, esi
  2197.         mov     edx, [esi+mchunk_prev_foot]
  2198.         sub     esi, [esi+mchunk_prev_foot]
  2199.         cmp     esi, [ebp+malloc_state.dv]
  2200.         jz      .append_dv
  2201.         push    eax
  2202.         mov     eax, esi
  2203.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2204.         jae     .append_large
  2205.         unlink_small_chunk      ; ebp, eax, edx
  2206.         jmp     .append_common
  2207. .append_large:
  2208.         mov     ecx, [ebx+tchunk_release_fd]
  2209.         mov     esi, [ebx+tchunk_release_bk]
  2210.         cmp     [ecx+tchunk_release_bk], ebx
  2211.         jnz     heap_corrupted
  2212.         cmp     [esi+tchunk_release_fd], ebx
  2213.         jnz     heap_corrupted
  2214.         mov     [ecx+tchunk_release_bk], esi
  2215.         mov     [esi+tchunk_release_fd], ecx
  2216.         unlink_large_chunk      ; ebp, eax
  2217. .append_common:
  2218.         mov     esi, eax
  2219.         mov     edx, [esp]
  2220.         pop     eax
  2221.         sub     edx, esi
  2222. .insert_before:
  2223.         lea     ecx, [edx+PINUSE_BIT]
  2224.         mov     [esi+mchunk_head], ecx
  2225.         mov     [eax+mchunk_prev_foot], edx
  2226.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2227.         jb      .small_before
  2228.         lea     ebx, [ebp+malloc_state.release_list-tchunk_release_fd]
  2229.         mov     ecx, [ebp+malloc_state.release_list]
  2230.         cmp     [ecx+tchunk_release_bk], ebx
  2231.         jnz     heap_corrupted
  2232.         mov     [ebx+tchunk_release_fd], eax
  2233.         mov     [ecx+tchunk_release_bk], eax
  2234.         mov     [eax+tchunk_release_fd], ecx
  2235.         mov     [eax+tchunk_release_bk], ebx
  2236.         push    edi
  2237. macro after_insert label \{
  2238.         pop     edi
  2239.         jmp     label
  2240. \}
  2241.         insert_large_chunk <after_insert .common_before>        ; ebp, esi, edx
  2242. .small_before:
  2243.         insert_small_chunk      ; ebp, esi, edx
  2244. .common_before:
  2245. .aligned:
  2246. ; give back spare room at the end
  2247.         test    dword [eax+mchunk_head], INUSE_BITS
  2248.         jz      .done_after
  2249.         mov     ecx, [bytes]
  2250.         mov     edx, [eax+mchunk_head]
  2251.         mov     ebx, edx
  2252.         and     edx, not FLAG_BITS
  2253.         lea     esi, [eax+ecx]
  2254.         sub     edx, ecx
  2255.         test    dword [esi+edx+mchunk_head], CINUSE_BIT
  2256.         jz      @f
  2257.         cmp     edx, MIN_CHUNK_SIZE
  2258.         jb      .done_after
  2259. @@:
  2260.         and     ebx, INUSE_BITS
  2261.         add     ebx, ecx
  2262.         mov     [eax+mchunk_head], ebx
  2263.         mark_inuse_foot esi
  2264.         test    dword [esi+edx+mchunk_head], CINUSE_BIT
  2265.         jnz     .insert_after
  2266.         add     esi, edx
  2267.         cmp     esi, [ebp+malloc_state.dv]
  2268.         jz      .prepend_dv
  2269.         cmp     esi, [ebp+malloc_state.top]
  2270.         jz      .prepend_top
  2271.         mov     edx, [esi+mchunk_head]
  2272.         and     edx, not FLAG_BITS
  2273.         push    eax
  2274.         mov     eax, esi
  2275.         add     esi, edx
  2276.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2277.         jae     .prepend_large
  2278.         unlink_small_chunk      ; ebp, eax, edx
  2279.         jmp     .prepend_common
  2280. .prepend_large:
  2281.         mov     ecx, [esi+tchunk_release_fd]
  2282.         mov     ebx, [esi+tchunk_release_bk]
  2283.         cmp     [ecx+tchunk_release_bk], esi
  2284.         jnz     heap_corrupted
  2285.         cmp     [ebx+tchunk_release_fd], esi
  2286.         jnz     heap_corrupted
  2287.         mov     [ecx+tchunk_release_bk], ebx
  2288.         mov     [ebx+tchunk_release_fd], ecx
  2289.         mov     ecx, esi
  2290.         unlink_large_chunk      ; ebp, eax
  2291.         mov     esi, ecx
  2292. .prepend_common:
  2293.         pop     eax
  2294.         mov     edx, esi
  2295.         mov     esi, [bytes]
  2296.         add     esi, eax
  2297.         sub     edx, esi
  2298. .insert_after:
  2299.         lea     ebx, [edx+PINUSE_BIT]
  2300.         mov     [esi+mchunk_head], ebx
  2301.         mov     [esi+edx+mchunk_prev_foot], edx
  2302.         and     dword [esi+edx+mchunk_head], not PINUSE_BIT
  2303.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2304.         jb      .small_after
  2305.         push    edi
  2306.         lea     ebx, [ebp+malloc_state.release_list-tchunk_release_fd]
  2307.         mov     ecx, [ebp+malloc_state.release_list]
  2308.         lea     edi, [esi+edx]
  2309.         cmp     [ecx+tchunk_release_bk], ebx
  2310.         jnz     heap_corrupted
  2311.         mov     [ebx+tchunk_release_fd], edi
  2312.         mov     [ecx+tchunk_release_bk], edi
  2313.         mov     [edi+tchunk_release_fd], ecx
  2314.         mov     [edi+tchunk_release_bk], ebx
  2315.         insert_large_chunk <after_insert .done_after>   ; ebp, esi, edx
  2316. purge after_insert
  2317. .small_after:
  2318.         insert_small_chunk      ; ebp, esi, edx
  2319. .done_after:
  2320.         unlock_heap
  2321.         ret
  2322. .prepend_dv:
  2323.         sub     esi, edx
  2324.         add     edx, [ebp+malloc_state.dvsize]
  2325.         mov     [ebp+malloc_state.dv], esi
  2326.         lea     ecx, [edx+PINUSE_BIT]
  2327.         mov     [esi+mchunk_head], ecx
  2328.         mov     [esi+edx+mchunk_prev_foot], edx
  2329.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2330.         jb      .prepend_dv.norelease
  2331.         add     esi, edx
  2332.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  2333.         jb      @f
  2334.         cmp     [esi+tchunk_release_fd], esi
  2335.         jnz     .prepend_dv.norelease
  2336. @@:
  2337.         lea     ebx, [ebp+malloc_state.release_list-tchunk_release_fd]
  2338.         mov     ecx, [ebp+malloc_state.release_list]
  2339.         cmp     [ecx+tchunk_release_bk], ebx
  2340.         jnz     heap_corrupted
  2341.         mov     [ebx+tchunk_release_fd], esi
  2342.         mov     [ecx+tchunk_release_bk], esi
  2343.         mov     [esi+tchunk_release_fd], ecx
  2344.         mov     [esi+tchunk_release_bk], ebx
  2345. .prepend_dv.norelease:
  2346.         mov     [ebp+malloc_state.dvsize], edx
  2347.         unlock_heap
  2348.         ret
  2349. .prepend_top:
  2350.         sub     esi, edx
  2351.         mov     [ebp+malloc_state.top], esi
  2352.         add     edx, [ebp+malloc_state.topsize]
  2353.         mov     [ebp+malloc_state.topsize], edx
  2354. assert PINUSE_BIT = 1
  2355.         inc     edx
  2356.         mov     [esi+mchunk_head], edx
  2357.         unlock_heap
  2358.         ret
  2359. .append_dv:
  2360.         mov     edx, eax
  2361.         sub     edx, esi
  2362.         cmp     edx, NSMALLBINS shl SMALLBIN_SHIFT
  2363.         jb      .append_dv.norelease
  2364.         cmp     [ebp+malloc_state.dvsize], NSMALLBINS shl SMALLBIN_SHIFT
  2365.         jb      @f
  2366.         cmp     [eax+tchunk_release_fd], eax
  2367.         jnz     .append_dv.norelease
  2368. @@:
  2369.         lea     ebx, [ebp+malloc_state.release_list-tchunk_release_fd]
  2370.         mov     ecx, [ebp+malloc_state.release_list]
  2371.         cmp     [ecx+tchunk_release_bk], ebx
  2372.         jnz     heap_corrupted
  2373.         mov     [ebx+tchunk_release_fd], eax
  2374.         mov     [ecx+tchunk_release_bk], eax
  2375.         mov     [eax+tchunk_release_fd], ecx
  2376.         mov     [eax+tchunk_release_bk], ebx
  2377. .append_dv.norelease:
  2378.         lea     ecx, [edx+PINUSE_BIT]
  2379.         mov     [ebp+malloc_state.dvsize], edx
  2380.         mov     [eax+mchunk_prev_foot], edx
  2381.         mov     [esi+mchunk_head], ecx
  2382.         jmp     .common_before
  2383. .unaligned_mmapped:
  2384. ; For mmapped chunks, just adjust offset
  2385.         mov     ecx, [esi+mchunk_head]
  2386.         sub     ecx, edx
  2387.         add     edx, [esi+mchunk_prev_foot]
  2388.         mov     [eax+mchunk_prev_foot], edx
  2389.         mov     [eax+mchunk_head], ecx
  2390.         unlock_heap
  2391.         ret
  2392. .too_large:
  2393.         mov     FS_ERRNO, ENOMEM
  2394.         xor     eax, eax
  2395. .nothing:
  2396.         ret
  2397. .set_to_min_chunk_size:
  2398.         mov     eax, MIN_CHUNK_SIZE
  2399.         mov     [alignment], eax
  2400.         jmp     .alignment_ok
  2401. .set_align_pow2:
  2402.         bsr     ecx, eax
  2403.         mov     eax, 2
  2404.         shl     eax, cl
  2405.         mov     [alignment], eax
  2406.         jmp     .alignment_ok
  2407. .just_malloc:
  2408.         malloc_call [bytes]
  2409.         ret
  2410. }
  2411.  
  2412. macro do_malloc_trim
  2413. {
  2414.         ret
  2415. }
  2416.  
  2417. macro do_malloc_footprint
  2418. {
  2419.         mov     eax, [ebp+malloc_state.footprint]
  2420.         ret
  2421. }
  2422.  
  2423. macro do_malloc_max_footprint
  2424. {
  2425.         mov     eax, [ebp+malloc_state.max_footprint]
  2426.         ret
  2427. }
  2428.  
  2429. macro do_malloc_footprint_limit
  2430. {
  2431.         mov     eax, [ebp+malloc_state.footprint_limit]
  2432.         test    eax, eax
  2433.         jnz     @f
  2434.         dec     eax
  2435. @@:
  2436.         ret
  2437. }
  2438.  
  2439. macro do_malloc_set_footprint_limit
  2440. {
  2441.         mov     eax, [bytes]
  2442.         test    eax, eax
  2443.         jnz     @f
  2444.         inc     eax
  2445. @@:
  2446.         cmp     eax, -1
  2447.         jnz     @f
  2448.         inc     eax
  2449. @@:
  2450.         add     eax, 0xFFF
  2451.         and     eax, not 0xFFF
  2452.         mov     [ebp+malloc_state.footprint_limit], eax
  2453.         ret
  2454. }
  2455.  
  2456. macro do_mspace_mallopt
  2457. {
  2458. }
  2459.  
  2460. ; ----------------------------- user mspaces ----------------------------
  2461.  
  2462. malloc_state_chunk_size = (sizeof.malloc_state + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) and not CHUNK_ALIGN_MASK
  2463. macro init_user_mstate
  2464. {
  2465.         mov     ebx, eax
  2466.         add     eax, 8 + ((-8) and CHUNK_ALIGN_MASK)
  2467.         mov     dword [eax+mchunk_head], malloc_state_chunk_size + INUSE_BITS
  2468.         mov     [eax+malloc_state.mmap_threshold], DEFAULT_MMAP_THRESHOLD
  2469.         mov     [eax+malloc_state.seg.base], ebx
  2470.         mov     [eax+malloc_state.seg.size], ecx
  2471.         mov     [eax+malloc_state.segment_size], ecx
  2472.         mov     [eax+malloc_state.footprint], ecx
  2473.         mov     [eax+malloc_state.max_footprint], ecx
  2474.         lea     ecx, [ecx+ebx+8-TOP_FOOT_SIZE]
  2475. if FOOTERS
  2476.         mov     ebx, [malloc_magic]
  2477.         mov     [eax+malloc_state.magic], ebx
  2478. end if
  2479.         mov     [eax+malloc_state.release_checks], RELEASE_CHECK_RATE
  2480.         init_bins       ; eax
  2481.         lea     ebx, [eax+malloc_state.release_list-tchunk_release_fd]
  2482.         mov     [eax+malloc_state.release_list+0], ebx
  2483.         mov     [eax+malloc_state.release_list+4], ebx
  2484.         lea     ebx, [eax+malloc_state.mmap_list]
  2485.         mov     [eax+malloc_state.mmap_list], ebx
  2486.         mov     [eax+malloc_state.mmap_list+4], ebx
  2487.         lea     ebx, [eax+malloc_state_chunk_size]
  2488.         sub     ecx, ebx
  2489.         init_top        ; eax, ebx, ecx
  2490. }
  2491.  
  2492. ; in: [capacity] = stack var with number of bytes to allocate
  2493. ; in: [locked] = stack var which is zero if locking is not needed
  2494. ; out: eax -> allocated data
  2495. macro do_create_mspace
  2496. {
  2497.         mov     eax, 68
  2498.         mov     ebx, 12
  2499.         mov     ecx, [capacity]
  2500.         test    ecx, ecx
  2501.         jnz     @f
  2502.         mov     ecx, DEFAULT_MSPACE_SIZE
  2503. @@:
  2504.         add     ecx, 0xFFF
  2505.         and     ecx, not 0xFFF
  2506.         jz      .fail
  2507.         call    FS_SYSCALL_PTR
  2508.         test    eax, eax
  2509.         jz      .fail
  2510.         init_user_mstate
  2511.         and     [eax+malloc_state.mflags], not USE_LOCK_BIT
  2512.         cmp     [locked], 0
  2513.         jz      @f
  2514.         or      [eax+malloc_state.mflags], USE_LOCK_BIT
  2515. @@:
  2516.         ret
  2517. .fail:
  2518.         xor     eax, eax
  2519.         ret
  2520. }
  2521.  
  2522. ; in: [msp] = stack var with mspace to free
  2523. macro do_destroy_mspace
  2524. {
  2525.         mov     edx, [msp]
  2526. if FOOTERS
  2527.         mov     ebx, [malloc_magic]
  2528.         cmp     [edx+malloc_state.magic], ebx
  2529.         jnz     heap_corrupted
  2530. end if
  2531.         add     edx, malloc_state.mmap_list
  2532.         push    edx
  2533.         mov     ecx, [edx]
  2534.         cmp     ecx, [esp]
  2535.         jz      .large_done
  2536. @@:
  2537.         mov     eax, 68
  2538.         mov     ebx, 13
  2539.         mov     edx, [ecx]
  2540.         call    FS_SYSCALL_PTR
  2541.         mov     ecx, edx
  2542.         cmp     edx, [esp]
  2543.         jnz     @b
  2544. .large_done:
  2545.         pop     edx
  2546.         add     edx, malloc_state.seg - malloc_state.mmap_list
  2547. .free_segments:
  2548.         mov     eax, 68
  2549.         mov     ebx, 13
  2550.         mov     ecx, [edx+malloc_segment.base]
  2551.         mov     edx, [edx+malloc_segment.next]
  2552.         call    FS_SYSCALL_PTR
  2553.         test    edx, edx
  2554.         jnz     .free_segments
  2555.         ret
  2556. }
  2557.