Skip to content

Commit a0b57d2

Browse files
joetifa2003joetifa2003
committed
update
1 parent 6716939 commit a0b57d2

File tree

2 files changed

+71
-107
lines changed

2 files changed

+71
-107
lines changed

‎mmapallocator/mmap.go

Lines changed: 67 additions & 98 deletions
Original file line numberDiff line numberDiff line change
@@ -10,26 +10,48 @@ import (
1010
"github.com/joetifa2003/mm-go/allocator"
1111
)
1212

13-
type mmapMeta struct {
14-
size int
13+
const (
14+
sizeClassCount = 9
15+
bigSizeClass = -1
16+
)
17+
18+
var sizeClasses = [sizeClassCount]int{32, 64, 128, 256, 512, 1024, 2048, 4096, bigSizeClass}
19+
20+
func getSizeClass(size int) (int, int) {
21+
for i, sizeClass := range sizeClasses {
22+
if size <= sizeClass {
23+
return i, sizeClass
24+
}
25+
}
26+
27+
return len(sizeClasses) - 1, bigSizeClass
28+
}
29+
30+
var freeLists [sizeClassCount]*block
31+
32+
type block struct {
33+
data unsafe.Pointer
1534
chunk *chunk
35+
next *block
36+
size int
37+
}
38+
39+
type ptrMeta struct {
40+
block *block
1641
}
1742

1843
type chunk struct {
1944
data unsafe.Pointer
2045
offset uintptr
2146
size uintptr
2247
ptrs uintptr
23-
next *chunk
24-
prev *chunk
2548
}
2649

2750
var pageSize = os.Getpagesize() * 15
2851

29-
var chunkHead *chunk
30-
3152
const (
32-
sizeOfPtrMeta = unsafe.Sizeof(mmapMeta{})
53+
sizeOfPtrMeta = unsafe.Sizeof(ptrMeta{})
54+
sizeOfBlock = unsafe.Sizeof(block{})
3355
sizeOfChunk = unsafe.Sizeof(chunk{})
3456
alignment = unsafe.Alignof(uintptr(0))
3557
)
@@ -39,107 +61,54 @@ func NewMMapAllocator() allocator.Allocator {
3961
}
4062

4163
func mmap_alloc(allocator unsafe.Pointer, size int) unsafe.Pointer {
42-
var viableChunk *chunk
43-
currentChunk := chunkHead
44-
45-
for currentChunk != nil {
46-
if currentChunk.offset+uintptr(size)+sizeOfPtrMeta <= currentChunk.size {
47-
viableChunk = currentChunk
48-
break
49-
}
50-
currentChunk = currentChunk.next
64+
sizeClassIdx, sizeClass := getSizeClass(int(sizeOfPtrMeta) + size)
65+
66+
b := freeLists[sizeClassIdx]
67+
if b != nil {
68+
ptrMeta := (*ptrMeta)(unsafe.Pointer(uintptr(b.data)))
69+
ptrMeta.block = b
70+
b.chunk.ptrs++
71+
freeLists[sizeClassIdx] = b.next
72+
return unsafe.Pointer(uintptr(unsafe.Pointer(ptrMeta)) + sizeOfPtrMeta)
5173
}
5274

53-
if viableChunk == nil {
54-
totalSize := int(mm.Align(uintptr(size)+sizeOfChunk+sizeOfPtrMeta, uintptr(pageSize)))
55-
res, err := mmap.MapRegion(nil, totalSize, mmap.RDWR, mmap.ANON, 0)
56-
if err != nil {
57-
panic(err)
58-
}
59-
60-
viableChunk = (*chunk)(unsafe.Pointer(&res[0]))
61-
viableChunk.data = unsafe.Pointer(uintptr(unsafe.Pointer(&res[0])) + sizeOfChunk)
62-
viableChunk.size = uintptr(totalSize - int(sizeOfChunk))
63-
viableChunk.offset = 0
64-
viableChunk.ptrs = 0
65-
66-
if chunkHead != nil {
67-
viableChunk.next = chunkHead
68-
chunkHead.prev = viableChunk
69-
chunkHead = viableChunk
70-
} else {
71-
chunkHead = viableChunk
72-
}
75+
// init size class
76+
totalSize := mm.Align(sizeOfChunk+uintptr(sizeClass)+sizeOfBlock, uintptr(pageSize))
77+
m, err := mmap.MapRegion(nil, int(totalSize), mmap.RDWR, mmap.ANON, 0)
78+
if err != nil {
79+
panic(err)
7380
}
7481

75-
ptrMeta := (*mmapMeta)(unsafe.Pointer(uintptr(viableChunk.data) + viableChunk.offset))
76-
ptrMeta.size = size
77-
ptrMeta.chunk = viableChunk
78-
viableChunk.offset = mm.Align(viableChunk.offset+uintptr(size)+sizeOfPtrMeta, alignment)
79-
viableChunk.ptrs++
82+
chunk := (*chunk)(unsafe.Pointer(&m[0]))
83+
chunk.data = unsafe.Pointer(unsafe.Pointer(&m[sizeOfChunk]))
84+
chunk.offset = 0
85+
chunk.size = totalSize - sizeOfChunk
86+
87+
nBlocks := chunk.size / (uintptr(sizeClass) + sizeOfBlock)
88+
for i := uintptr(0); i < nBlocks; i++ {
89+
b := (*block)(unsafe.Pointer(uintptr(chunk.data) + uintptr(i*sizeOfBlock)))
90+
b.data = unsafe.Pointer(uintptr(chunk.data) + uintptr(i*(uintptr(sizeClass)+sizeOfBlock)))
91+
b.next = freeLists[sizeClassIdx]
92+
b.size = sizeClass
93+
b.chunk = chunk
94+
freeLists[sizeClassIdx] = b
95+
}
8096

81-
ptr := unsafe.Pointer(uintptr(unsafe.Pointer(ptrMeta)) + uintptr(sizeOfPtrMeta))
82-
return ptr
97+
return mmap_alloc(allocator, size)
8398
}
8499

85100
func mmap_free(allocator unsafe.Pointer, ptr unsafe.Pointer) {
86-
ptrMeta := (*mmapMeta)(unsafe.Pointer(uintptr(ptr) - sizeOfPtrMeta))
87-
chunk := ptrMeta.chunk
88-
chunk.ptrs--
89-
90-
if chunk.ptrs == 0 {
91-
if chunk == chunkHead {
92-
chunkHead = chunkHead.next
93-
} else {
94-
if chunk.prev != nil {
95-
chunk.prev.next = chunk.next
96-
}
97-
98-
if chunk.next != nil {
99-
chunk.next.prev = chunk.prev
100-
}
101-
}
102-
103-
m := mmap.MMap(
104-
unsafe.Slice(
105-
(*byte)(
106-
unsafe.Pointer(uintptr(chunk.data)-sizeOfChunk),
107-
), chunk.size+sizeOfChunk),
108-
)
109-
err := m.Unmap()
110-
if err != nil {
111-
panic(err)
112-
}
113-
}
101+
ptrMeta := (*ptrMeta)(unsafe.Pointer(uintptr(ptr) - sizeOfPtrMeta))
102+
block := ptrMeta.block
103+
sizeClassIdx, _ := getSizeClass(block.size)
104+
block.chunk.ptrs--
105+
head := freeLists[sizeClassIdx]
106+
block.next = head
107+
freeLists[sizeClassIdx] = block
114108
}
115109

116110
func mmap_realloc(allocator unsafe.Pointer, ptr unsafe.Pointer, size int) unsafe.Pointer {
117-
oldMeta := (*mmapMeta)(unsafe.Pointer(uintptr(ptr) - sizeOfPtrMeta))
118-
oldData := unsafe.Slice((*byte)(ptr), oldMeta.size)
119-
newPtr := mmap_alloc(allocator, size)
120-
newData := unsafe.Slice((*byte)(newPtr), size)
121-
copy(newData, oldData)
122-
mmap_free(allocator, ptr)
123-
124-
return newPtr
111+
return nil
125112
}
126113

127-
func mmap_destroy(allocator unsafe.Pointer) {
128-
currentChunk := chunkHead
129-
for currentChunk != nil {
130-
nextChunk := currentChunk.next
131-
m := mmap.MMap(
132-
unsafe.Slice(
133-
(*byte)(
134-
unsafe.Pointer(uintptr(currentChunk.data)-sizeOfChunk),
135-
), currentChunk.size+sizeOfChunk),
136-
)
137-
err := m.Unmap()
138-
if err != nil {
139-
panic(err)
140-
}
141-
currentChunk = nextChunk
142-
}
143-
144-
chunkHead = nil
145-
}
114+
func mmap_destroy(allocator unsafe.Pointer) {}

‎mmapallocator/mmap_test.go

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -4,25 +4,20 @@ import (
44
"testing"
55

66
"github.com/joetifa2003/mm-go/allocator"
7-
"github.com/joetifa2003/mm-go/batchallocator"
87
"github.com/joetifa2003/mm-go/mmapallocator"
98
)
109

1110
func TestMMapAllocator(t *testing.T) {
12-
alloc := batchallocator.New(mmapallocator.NewMMapAllocator())
11+
alloc := mmapallocator.NewMMapAllocator()
1312

1413
ptr := allocator.Alloc[int](alloc)
1514
*ptr = 1
1615
ptr2 := allocator.Alloc[int](alloc)
1716
*ptr2 = 2
1817
allocator.Free(alloc, ptr2)
18+
ptr3 := allocator.Alloc[int](alloc)
19+
_ = ptr3
1920
allocator.Free(alloc, ptr)
21+
allocator.Free(alloc, ptr3)
2022
alloc.Destroy()
21-
22-
alloc2 := batchallocator.New(mmapallocator.NewMMapAllocator())
23-
24-
ptr = allocator.Alloc[int](alloc2)
25-
*ptr = 5
26-
27-
alloc2.Destroy()
2823
}

0 commit comments

Comments
 (0)