diff options
Diffstat (limited to 'lib/system/alloc.nim')
| -rw-r--r-- | lib/system/alloc.nim | 208 |
1 files changed, 104 insertions, 104 deletions
diff --git a/lib/system/alloc.nim b/lib/system/alloc.nim index fd3ced832..ad3419808 100644 --- a/lib/system/alloc.nim +++ b/lib/system/alloc.nim @@ -8,7 +8,7 @@ # # Low level allocator for Nim. Has been designed to support the GC. -# TODO: +# TODO: # - eliminate "used" field # - make searching for block O(1) {.push profiler:off.} @@ -21,37 +21,37 @@ # used with a size of 0: const weirdUnmap = not (defined(amd64) or defined(i386)) or defined(windows) -when defined(posix): +when defined(posix): const - PROT_READ = 1 # page can be read - PROT_WRITE = 2 # page can be written - MAP_PRIVATE = 2'i32 # Changes are private - + PROT_READ = 1 # page can be read + PROT_WRITE = 2 # page can be written + MAP_PRIVATE = 2'i32 # Changes are private + when defined(macosx) or defined(bsd): const MAP_ANONYMOUS = 0x1000 - elif defined(solaris): + elif defined(solaris): const MAP_ANONYMOUS = 0x100 else: var MAP_ANONYMOUS {.importc: "MAP_ANONYMOUS", header: "<sys/mman.h>".}: cint - + proc mmap(adr: pointer, len: int, prot, flags, fildes: cint, off: int): pointer {.header: "<sys/mman.h>".} proc munmap(adr: pointer, len: int) {.header: "<sys/mman.h>".} - - proc osAllocPages(size: int): pointer {.inline.} = - result = mmap(nil, size, PROT_READ or PROT_WRITE, + + proc osAllocPages(size: int): pointer {.inline.} = + result = mmap(nil, size, PROT_READ or PROT_WRITE, MAP_PRIVATE or MAP_ANONYMOUS, -1, 0) if result == nil or result == cast[pointer](-1): raiseOutOfMem() - + proc osDeallocPages(p: pointer, size: int) {.inline} = when reallyOsDealloc: munmap(p, size) - -elif defined(windows): + +elif defined(windows): const - MEM_RESERVE = 0x2000 + MEM_RESERVE = 0x2000 MEM_COMMIT = 0x1000 MEM_TOP_DOWN = 0x100000 PAGE_READWRITE = 0x04 @@ -62,12 +62,12 @@ elif defined(windows): proc virtualAlloc(lpAddress: pointer, dwSize: int, flAllocationType, flProtect: int32): pointer {. header: "<windows.h>", stdcall, importc: "VirtualAlloc".} - - proc virtualFree(lpAddress: pointer, dwSize: int, + + proc virtualFree(lpAddress: pointer, dwSize: int, dwFreeType: int32) {.header: "<windows.h>", stdcall, importc: "VirtualFree".} - - proc osAllocPages(size: int): pointer {.inline.} = + + proc osAllocPages(size: int): pointer {.inline.} = result = virtualAlloc(nil, size, MEM_RESERVE or MEM_COMMIT, PAGE_READWRITE) if result == nil: raiseOutOfMem() @@ -82,7 +82,7 @@ elif defined(windows): when reallyOsDealloc: virtualFree(p, 0, MEM_RELEASE) #VirtualFree(p, size, MEM_DECOMMIT) -else: +else: {.error: "Port memory manager to your platform".} # --------------------- end of non-portable code ----------------------------- @@ -97,17 +97,17 @@ const InitialMemoryRequest = ChunkOsReturn div 2 # < ChunkOsReturn! SmallChunkSize = PageSize -type +type PTrunk = ptr TTrunk - TTrunk {.final.} = object + TTrunk {.final.} = object next: PTrunk # all nodes are connected with this pointer key: int # start address at bit 0 bits: array[0..IntsPerTrunk-1, int] # a bit vector - + TTrunkBuckets = array[0..255, PTrunk] - TIntSet {.final.} = object + TIntSet {.final.} = object data: TTrunkBuckets - + type TAlignType = BiggestFloat TFreeCell {.final, pure.} = object @@ -123,14 +123,14 @@ type prevSize: int # size of previous chunk; for coalescing size: int # if < PageSize it is a small chunk used: bool # later will be optimized into prevSize... - + TSmallChunk = object of TBaseChunk next, prev: PSmallChunk # chunks of the same size freeList: ptr TFreeCell - free: int # how many bytes remain + free: int # how many bytes remain acc: int # accumulator for small object allocation data: TAlignType # start of usable memory - + TBigChunk = object of TBaseChunk # not necessarily > PageSize! next, prev: PBigChunk # chunks of the same (or bigger) size align: int @@ -139,7 +139,7 @@ type template smallChunkOverhead(): expr = sizeof(TSmallChunk)-sizeof(TAlignType) template bigChunkOverhead(): expr = sizeof(TBigChunk)-sizeof(TAlignType) -proc roundup(x, v: int): int {.inline.} = +proc roundup(x, v: int): int {.inline.} = result = (x + (v-1)) and not (v-1) sysAssert(result >= x, "roundup: result < x") #return ((-x) and (v-1)) +% x @@ -153,7 +153,7 @@ sysAssert(roundup(65, 8) == 72, "roundup broken 2") # endings of big chunks. This is needed by the merging operation. The only # remaining operation is best-fit for big chunks. Since there is a size-limit # for big chunks (because greater than the limit means they are returned back -# to the OS), a fixed size array can be used. +# to the OS), a fixed size array can be used. type PLLChunk = ptr TLLChunk @@ -163,21 +163,21 @@ type next: PLLChunk # next low-level chunk; only needed for dealloc PAvlNode = ptr TAvlNode - TAvlNode {.pure, final.} = object - link: array[0..1, PAvlNode] # Left (0) and right (1) links + TAvlNode {.pure, final.} = object + link: array[0..1, PAvlNode] # Left (0) and right (1) links key, upperBound: int level: int - + TMemRegion {.final, pure.} = object minLargeObj, maxLargeObj: int freeSmallChunks: array[0..SmallChunkSize div MemAlign-1, PSmallChunk] llmem: PLLChunk currMem, maxMem, freeMem: int # memory sizes (allocated from OS) - lastSize: int # needed for the case that OS gives us pages linearly + lastSize: int # needed for the case that OS gives us pages linearly freeChunksList: PBigChunk # XXX make this a datastructure with O(1) access chunkStarts: TIntSet root, deleted, last, freeAvlNodes: PAvlNode - + # shared: var bottomData: TAvlNode @@ -191,7 +191,7 @@ proc initAllocator() = bottom.link[1] = bottom {.pop.} -proc incCurrMem(a: var TMemRegion, bytes: int) {.inline.} = +proc incCurrMem(a: var TMemRegion, bytes: int) {.inline.} = inc(a.currMem, bytes) proc decCurrMem(a: var TMemRegion, bytes: int) {.inline.} = @@ -199,11 +199,11 @@ proc decCurrMem(a: var TMemRegion, bytes: int) {.inline.} = dec(a.currMem, bytes) proc getMaxMem(a: var TMemRegion): int = - # Since we update maxPagesCount only when freeing pages, + # Since we update maxPagesCount only when freeing pages, # maxPagesCount may not be up to date. Thus we use the # maximum of these both values here: result = max(a.currMem, a.maxMem) - + proc llAlloc(a: var TMemRegion, size: int): pointer = # *low-level* alloc for the memory managers data structures. Deallocation # is done at he end of the allocator's life time. @@ -251,15 +251,15 @@ proc llDeallocAll(a: var TMemRegion) = var next = it.next osDeallocPages(it, PageSize) it = next - -proc intSetGet(t: TIntSet, key: int): PTrunk = + +proc intSetGet(t: TIntSet, key: int): PTrunk = var it = t.data[key and high(t.data)] - while it != nil: + while it != nil: if it.key == key: return it it = it.next result = nil -proc intSetPut(a: var TMemRegion, t: var TIntSet, key: int): PTrunk = +proc intSetPut(a: var TMemRegion, t: var TIntSet, key: int): PTrunk = result = intSetGet(t, key) if result == nil: result = cast[PTrunk](llAlloc(a, sizeof(result[]))) @@ -267,20 +267,20 @@ proc intSetPut(a: var TMemRegion, t: var TIntSet, key: int): PTrunk = t.data[key and high(t.data)] = result result.key = key -proc contains(s: TIntSet, key: int): bool = +proc contains(s: TIntSet, key: int): bool = var t = intSetGet(s, key shr TrunkShift) - if t != nil: + if t != nil: var u = key and TrunkMask result = (t.bits[u shr IntShift] and (1 shl (u and IntMask))) != 0 - else: + else: result = false - -proc incl(a: var TMemRegion, s: var TIntSet, key: int) = + +proc incl(a: var TMemRegion, s: var TIntSet, key: int) = var t = intSetPut(a, s, key shr TrunkShift) var u = key and TrunkMask t.bits[u shr IntShift] = t.bits[u shr IntShift] or (1 shl (u and IntMask)) -proc excl(s: var TIntSet, key: int) = +proc excl(s: var TIntSet, key: int) = var t = intSetGet(s, key shr TrunkShift) if t != nil: var u = key and TrunkMask @@ -304,11 +304,11 @@ iterator elements(t: TIntSet): int {.inline.} = w = w shr 1 inc(i) r = r.next - -proc isSmallChunk(c: PChunk): bool {.inline.} = + +proc isSmallChunk(c: PChunk): bool {.inline.} = return c.size <= SmallChunkSize-smallChunkOverhead() - -proc chunkUnused(c: PChunk): bool {.inline.} = + +proc chunkUnused(c: PChunk): bool {.inline.} = result = not c.used iterator allObjects(m: TMemRegion): pointer {.inline.} = @@ -319,7 +319,7 @@ iterator allObjects(m: TMemRegion): pointer {.inline.} = if not chunkUnused(c): if isSmallChunk(c): var c = cast[PSmallChunk](c) - + let size = c.size var a = cast[ByteAddress](addr(c.data)) let limit = a + c.acc @@ -334,17 +334,17 @@ proc isCell(p: pointer): bool {.inline.} = result = cast[ptr TFreeCell](p).zeroField >% 1 # ------------- chunk management ---------------------------------------------- -proc pageIndex(c: PChunk): int {.inline.} = +proc pageIndex(c: PChunk): int {.inline.} = result = cast[ByteAddress](c) shr PageShift -proc pageIndex(p: pointer): int {.inline.} = +proc pageIndex(p: pointer): int {.inline.} = result = cast[ByteAddress](p) shr PageShift -proc pageAddr(p: pointer): PChunk {.inline.} = +proc pageAddr(p: pointer): PChunk {.inline.} = result = cast[PChunk](cast[ByteAddress](p) and not PageMask) #sysAssert(Contains(allocator.chunkStarts, pageIndex(result))) -proc requestOsChunks(a: var TMemRegion, size: int): PBigChunk = +proc requestOsChunks(a: var TMemRegion, size: int): PBigChunk = incCurrMem(a, size) inc(a.freeMem, size) result = cast[PBigChunk](osAllocPages(size)) @@ -373,7 +373,7 @@ proc requestOsChunks(a: var TMemRegion, size: int): PBigChunk = result.prevSize = 0 # unknown a.lastSize = size # for next request -proc freeOsChunks(a: var TMemRegion, p: pointer, size: int) = +proc freeOsChunks(a: var TMemRegion, p: pointer, size: int) = # update next.prevSize: var c = cast[PChunk](p) var nxt = cast[ByteAddress](p) +% c.size @@ -387,36 +387,36 @@ proc freeOsChunks(a: var TMemRegion, p: pointer, size: int) = dec(a.freeMem, size) #c_fprintf(c_stdout, "[Alloc] back to OS: %ld\n", size) -proc isAccessible(a: TMemRegion, p: pointer): bool {.inline.} = +proc isAccessible(a: TMemRegion, p: pointer): bool {.inline.} = result = contains(a.chunkStarts, pageIndex(p)) -proc contains[T](list, x: T): bool = +proc contains[T](list, x: T): bool = var it = list while it != nil: if it == x: return true it = it.next - + proc writeFreeList(a: TMemRegion) = var it = a.freeChunksList c_fprintf(c_stdout, "freeChunksList: %p\n", it) - while it != nil: - c_fprintf(c_stdout, "it: %p, next: %p, prev: %p\n", + while it != nil: + c_fprintf(c_stdout, "it: %p, next: %p, prev: %p\n", it, it.next, it.prev) it = it.next -proc listAdd[T](head: var T, c: T) {.inline.} = +proc listAdd[T](head: var T, c: T) {.inline.} = sysAssert(c notin head, "listAdd 1") sysAssert c.prev == nil, "listAdd 2" sysAssert c.next == nil, "listAdd 3" c.next = head - if head != nil: + if head != nil: sysAssert head.prev == nil, "listAdd 4" head.prev = c head = c proc listRemove[T](head: var T, c: T) {.inline.} = sysAssert(c in head, "listRemove") - if c == head: + if c == head: head = c.next sysAssert c.prev == nil, "listRemove 2" if head != nil: head.prev = nil @@ -426,15 +426,15 @@ proc listRemove[T](head: var T, c: T) {.inline.} = if c.next != nil: c.next.prev = c.prev c.next = nil c.prev = nil - -proc updatePrevSize(a: var TMemRegion, c: PBigChunk, - prevSize: int) {.inline.} = + +proc updatePrevSize(a: var TMemRegion, c: PBigChunk, + prevSize: int) {.inline.} = var ri = cast[PChunk](cast[ByteAddress](c) +% c.size) sysAssert((cast[ByteAddress](ri) and PageMask) == 0, "updatePrevSize") if isAccessible(a, ri): ri.prevSize = prevSize - -proc freeBigChunk(a: var TMemRegion, c: PBigChunk) = + +proc freeBigChunk(a: var TMemRegion, c: PBigChunk) = var c = c sysAssert(c.size >= PageSize, "freeBigChunk") inc(a.freeMem, c.size) @@ -448,7 +448,7 @@ proc freeBigChunk(a: var TMemRegion, c: PBigChunk) = inc(c.size, ri.size) excl(a.chunkStarts, pageIndex(ri)) when coalescLeft: - if c.prevSize != 0: + if c.prevSize != 0: var le = cast[PChunk](cast[ByteAddress](c) -% c.prevSize) sysAssert((cast[ByteAddress](le) and PageMask) == 0, "freeBigChunk 4") if isAccessible(a, le) and chunkUnused(le): @@ -467,7 +467,7 @@ proc freeBigChunk(a: var TMemRegion, c: PBigChunk) = else: freeOsChunks(a, c, c.size) -proc splitChunk(a: var TMemRegion, c: PBigChunk, size: int) = +proc splitChunk(a: var TMemRegion, c: PBigChunk, size: int) = var rest = cast[PBigChunk](cast[ByteAddress](c) +% size) sysAssert(rest notin a.freeChunksList, "splitChunk") rest.size = c.size - size @@ -480,7 +480,7 @@ proc splitChunk(a: var TMemRegion, c: PBigChunk, size: int) = incl(a, a.chunkStarts, pageIndex(rest)) listAdd(a.freeChunksList, rest) -proc getBigChunk(a: var TMemRegion, size: int): PBigChunk = +proc getBigChunk(a: var TMemRegion, size: int): PBigChunk = # use first fit for now: sysAssert((size and PageMask) == 0, "getBigChunk 1") sysAssert(size > 0, "getBigChunk 2") @@ -488,7 +488,7 @@ proc getBigChunk(a: var TMemRegion, size: int): PBigChunk = block search: while result != nil: sysAssert chunkUnused(result), "getBigChunk 3" - if result.size == size: + if result.size == size: listRemove(a.freeChunksList, result) break search elif result.size > size: @@ -497,7 +497,7 @@ proc getBigChunk(a: var TMemRegion, size: int): PBigChunk = break search result = result.next sysAssert result != a.freeChunksList, "getBigChunk 4" - if size < InitialMemoryRequest: + if size < InitialMemoryRequest: result = requestOsChunks(a, InitialMemoryRequest) splitChunk(a, result, size) else: @@ -507,7 +507,7 @@ proc getBigChunk(a: var TMemRegion, size: int): PBigChunk = incl(a, a.chunkStarts, pageIndex(result)) dec(a.freeMem, size) -proc getSmallChunk(a: var TMemRegion): PSmallChunk = +proc getSmallChunk(a: var TMemRegion): PSmallChunk = var res = getBigChunk(a, PageSize) sysAssert res.prev == nil, "getSmallChunk 1" sysAssert res.next == nil, "getSmallChunk 2" @@ -521,15 +521,15 @@ proc allocInv(a: TMemRegion): bool = for s in low(a.freeSmallChunks)..high(a.freeSmallChunks): var c = a.freeSmallChunks[s] while c != nil: - if c.next == c: + if c.next == c: echo "[SYSASSERT] c.next == c" return false - if c.size != s * MemAlign: + if c.size != s * MemAlign: echo "[SYSASSERT] c.size != s * MemAlign" return false var it = c.freeList while it != nil: - if it.zeroField != 0: + if it.zeroField != 0: echo "[SYSASSERT] it.zeroField != 0" c_printf("%ld %p\n", it.zeroField, it) return false @@ -539,16 +539,16 @@ proc allocInv(a: TMemRegion): bool = proc rawAlloc(a: var TMemRegion, requestedSize: int): pointer = sysAssert(allocInv(a), "rawAlloc: begin") - sysAssert(roundup(65, 8) == 72, "rawAlloc 1") - sysAssert requestedSize >= sizeof(TFreeCell), "rawAlloc 2" + sysAssert(roundup(65, 8) == 72, "rawAlloc: roundup broken") + sysAssert(requestedSize >= sizeof(TFreeCell), "rawAlloc: requested size too small") var size = roundup(requestedSize, MemAlign) sysAssert(size >= requestedSize, "insufficient allocated size!") #c_fprintf(c_stdout, "alloc; size: %ld; %ld\n", requestedSize, size) - if size <= SmallChunkSize-smallChunkOverhead(): + if size <= SmallChunkSize-smallChunkOverhead(): # allocate a small block: for small chunks, we use only its next pointer var s = size div MemAlign var c = a.freeSmallChunks[s] - if c == nil: + if c == nil: c = getSmallChunk(a) c.freeList = nil sysAssert c.size == PageSize, "rawAlloc 3" @@ -567,7 +567,7 @@ proc rawAlloc(a: var TMemRegion, requestedSize: int): pointer = # c_fprintf(c_stdout, "csize: %lld; size %lld\n", c.size, size) sysAssert c.size == size, "rawAlloc 6" if c.freeList == nil: - sysAssert(c.acc + smallChunkOverhead() + size <= SmallChunkSize, + sysAssert(c.acc + smallChunkOverhead() + size <= SmallChunkSize, "rawAlloc 7") result = cast[pointer](cast[ByteAddress](addr(c.data)) +% c.acc) inc(c.acc, size) @@ -621,9 +621,9 @@ proc rawDealloc(a: var TMemRegion, p: pointer) = f.zeroField = 0 f.next = c.freeList c.freeList = f - when overwriteFree: + when overwriteFree: # set to 0xff to check for usage after free bugs: - c_memset(cast[pointer](cast[int](p) +% sizeof(TFreeCell)), -1'i32, + c_memset(cast[pointer](cast[int](p) +% sizeof(TFreeCell)), -1'i32, s -% sizeof(TFreeCell)) # check if it is not in the freeSmallChunks[s] list: if c.free < s: @@ -649,13 +649,13 @@ proc rawDealloc(a: var TMemRegion, p: pointer) = sysAssert(allocInv(a), "rawDealloc: end") when logAlloc: cprintf("rawDealloc: %p\n", p) -proc isAllocatedPtr(a: TMemRegion, p: pointer): bool = +proc isAllocatedPtr(a: TMemRegion, p: pointer): bool = if isAccessible(a, p): var c = pageAddr(p) if not chunkUnused(c): if isSmallChunk(c): var c = cast[PSmallChunk](c) - var offset = (cast[ByteAddress](p) and (PageSize-1)) -% + var offset = (cast[ByteAddress](p) and (PageSize-1)) -% smallChunkOverhead() result = (c.acc >% offset) and (offset %% c.size == 0) and (cast[ptr TFreeCell](p).zeroField >% 1) @@ -673,12 +673,12 @@ proc interiorAllocatedPtr(a: TMemRegion, p: pointer): pointer = if not chunkUnused(c): if isSmallChunk(c): var c = cast[PSmallChunk](c) - var offset = (cast[ByteAddress](p) and (PageSize-1)) -% + var offset = (cast[ByteAddress](p) and (PageSize-1)) -% smallChunkOverhead() if c.acc >% offset: sysAssert(cast[ByteAddress](addr(c.data)) +% offset == cast[ByteAddress](p), "offset is not what you think it is") - var d = cast[ptr TFreeCell](cast[ByteAddress](addr(c.data)) +% + var d = cast[ptr TFreeCell](cast[ByteAddress](addr(c.data)) +% offset -% (offset %% c.size)) if d.zeroField >% 1: result = d @@ -711,13 +711,13 @@ proc ptrSize(p: pointer): int = if not isSmallChunk(c): dec result, bigChunkOverhead() -proc alloc(allocator: var TMemRegion, size: int): pointer = +proc alloc(allocator: var TMemRegion, size: Natural): pointer = result = rawAlloc(allocator, size+sizeof(TFreeCell)) cast[ptr TFreeCell](result).zeroField = 1 # mark it as used sysAssert(not isAllocatedPtr(allocator, result), "alloc") result = cast[pointer](cast[ByteAddress](result) +% sizeof(TFreeCell)) -proc alloc0(allocator: var TMemRegion, size: int): pointer = +proc alloc0(allocator: var TMemRegion, size: Natural): pointer = result = alloc(allocator, size) zeroMem(result, size) @@ -730,7 +730,7 @@ proc dealloc(allocator: var TMemRegion, p: pointer) = rawDealloc(allocator, x) sysAssert(not isAllocatedPtr(allocator, x), "dealloc 3") -proc realloc(allocator: var TMemRegion, p: pointer, newsize: int): pointer = +proc realloc(allocator: var TMemRegion, p: pointer, newsize: Natural): pointer = if newsize > 0: result = alloc0(allocator, newsize) if p != nil: @@ -758,7 +758,7 @@ proc deallocOsPages(a: var TMemRegion) = proc getFreeMem(a: TMemRegion): int {.inline.} = result = a.freeMem proc getTotalMem(a: TMemRegion): int {.inline.} = result = a.currMem -proc getOccupiedMem(a: TMemRegion): int {.inline.} = +proc getOccupiedMem(a: TMemRegion): int {.inline.} = result = a.currMem - a.freeMem # ---------------------- thread memory region ------------------------------- @@ -774,16 +774,16 @@ template instantiateForRegion(allocator: expr) = proc deallocOsPages = deallocOsPages(allocator) - proc alloc(size: int): pointer = + proc alloc(size: Natural): pointer = result = alloc(allocator, size) - proc alloc0(size: int): pointer = + proc alloc0(size: Natural): pointer = result = alloc0(allocator, size) proc dealloc(p: pointer) = dealloc(allocator, p) - proc realloc(p: pointer, newsize: int): pointer = + proc realloc(p: pointer, newsize: Natural): pointer = result = realloc(allocator, p, newSize) when false: @@ -794,7 +794,7 @@ template instantiateForRegion(allocator: expr) = inc(result, it.size) it = it.next - proc getFreeMem(): int = + proc getFreeMem(): int = result = allocator.freeMem #sysAssert(result == countFreeMem()) @@ -807,7 +807,7 @@ template instantiateForRegion(allocator: expr) = var heapLock: TSysLock initSysLock(heapLock) - proc allocShared(size: int): pointer = + proc allocShared(size: Natural): pointer = when hasThreadSupport: acquireSys(heapLock) result = alloc(sharedHeap, size) @@ -815,20 +815,20 @@ template instantiateForRegion(allocator: expr) = else: result = alloc(size) - proc allocShared0(size: int): pointer = + proc allocShared0(size: Natural): pointer = result = allocShared(size) zeroMem(result, size) proc deallocShared(p: pointer) = - when hasThreadSupport: + when hasThreadSupport: acquireSys(heapLock) dealloc(sharedHeap, p) releaseSys(heapLock) else: dealloc(p) - proc reallocShared(p: pointer, newsize: int): pointer = - when hasThreadSupport: + proc reallocShared(p: pointer, newsize: Natural): pointer = + when hasThreadSupport: acquireSys(heapLock) result = realloc(sharedHeap, p, newsize) releaseSys(heapLock) |