Subversion Repositories Kolibri OS

Rev

Rev 5363 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2. ;;                                                              ;;
  3. ;; Copyright (C) KolibriOS team 2013-2015. All rights reserved. ;;
  4. ;; Distributed under terms of the GNU General Public License    ;;
  5. ;;                                                              ;;
  6. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  7.  
  8. $Revision: 8037 $
  9.  
  10. ; Memory management for slab structures.
  11. ; The allocator meets special requirements:
  12. ; * memory blocks are properly aligned
  13. ; * memory blocks do not cross page boundary
  14. ; The allocator manages fixed-size blocks.
  15. ; Thus, the specific allocator works as follows:
  16. ; allocate one page, split into blocks, maintain the single-linked
  17. ; list of all free blocks in each page.
  18.  
  19. ; Note: size must be a multiple of required alignment.
  20.  
  21. ; Data for one pool: dd pointer to the first page, MUTEX lock.
  22.  
  23. ; Allocator for fixed-size blocks: allocate a block.
  24. ; [ebx-4] = pointer to the first page, ebx = pointer to MUTEX structure.
  25. proc slab_alloc
  26.         push    edi     ; save used register to be stdcall
  27. virtual at esp
  28.         dd      ?       ; saved edi
  29.         dd      ?       ; return address
  30. .size   dd      ?
  31. end virtual
  32. ; 1. Take the lock.
  33.         mov     ecx, ebx
  34.         call    mutex_lock
  35. ; 2. Find the first allocated page with a free block, if any.
  36. ; 2a. Initialize for the loop.
  37.         mov     edx, ebx
  38. .pageloop:
  39. ; 2b. Get the next page, keeping the current in eax.
  40.         mov     eax, edx
  41.         mov     edx, [edx-4]
  42. ; 2c. If there is no next page, we're out of luck; go to 4.
  43.         test    edx, edx
  44.         jz      .newpage
  45.         add     edx, 0x1000
  46. @@:
  47. ; 2d. Get the pointer to the first free block on this page.
  48. ; If there is no free block, continue to 2b.
  49.         mov     eax, [edx-8]
  50.         test    eax, eax
  51.         jz      .pageloop
  52. ; 2e. Get the pointer to the next free block.
  53.         mov     ecx, [eax]
  54. ; 2f. Update the pointer to the first free block from eax to ecx.
  55. ; Normally [edx-8] still contains eax, if so, atomically set it to ecx
  56. ; and proceed to 3.
  57. ; However, the price of simplicity of slab_free (in particular, it doesn't take
  58. ; the lock) is that [edx-8] could (rarely) be changed while we processed steps
  59. ; 2d+2e. If so, return to 2d and retry.
  60.         lock cmpxchg [edx-8], ecx
  61.         jnz     @b
  62. .return:
  63. ; 3. Release the lock taken in step 1 and return.
  64.         push    eax
  65.         mov     ecx, ebx
  66.         call    mutex_unlock
  67.         pop     eax
  68.         pop     edi     ; restore used register to be stdcall
  69.         ret     4
  70. .newpage:
  71. ; 4. Allocate a new page.
  72.         push    eax
  73.         stdcall kernel_alloc, 0x1000
  74.         pop     edx
  75. ; If failed, say something to the debug board and return zero.
  76.         test    eax, eax
  77.         jz      .nomemory
  78. ; 5. Add the new page to the tail of list of allocated pages.
  79.         mov     [edx-4], eax
  80. ; 6. Initialize two service dwords in the end of page:
  81. ; first free block is (start of page) + (block size)
  82. ; (we will return first block at (start of page), so consider it allocated),
  83. ; no next page.
  84.         mov     edx, eax
  85.         lea     edi, [eax+0x1000-8]
  86.         add     edx, [.size]
  87.         mov     [edi], edx
  88.         and     dword [edi+4], 0
  89. ; 7. All blocks starting from edx are free; join them in a single-linked list.
  90. @@:
  91.         mov     ecx, edx
  92.         add     edx, [.size]
  93.         mov     [ecx], edx
  94.         cmp     edx, edi
  95.         jbe     @b
  96.         sub     ecx, [.size]
  97.         and     dword [ecx], 0
  98. ; 8. Return (start of page).
  99.         jmp     .return
  100. .nomemory:
  101.         dbgstr 'no memory for slab allocation'
  102.         xor     eax, eax
  103.         jmp     .return
  104. endp
  105.  
  106. ; Allocator for fixed-size blocks: free a block.
  107. proc slab_free
  108.         push    ecx edx
  109. virtual at esp
  110.         rd      2       ; saved registers
  111.         dd      ?       ; return address
  112. .block  dd      ?
  113. end virtual
  114. ; Insert the given block to the head of free blocks in this page.
  115.         mov     ecx, [.block]
  116.         mov     edx, ecx
  117.         or      edx, 0xFFF
  118. @@:
  119.         mov     eax, [edx+1-8]
  120.         mov     [ecx], eax
  121.         lock cmpxchg [edx+1-8], ecx
  122.         jnz     @b
  123.         pop     edx ecx
  124.         ret     4
  125. endp
  126.