source: code/trunk/vendor/modernc.org/memory/memory.go@ 824

Last change on this file since 824 was 822, checked in by yakumo.izuru, 22 months ago

Prefer immortal.run over runit and rc.d, use vendored modules
for convenience.

Signed-off-by: Izuru Yakumo <yakumo.izuru@…>
File size: 18.2 KB
Line 
1// Copyright 2017 The Memory Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5// Package memory implements a memory allocator.
6//
7// Build status
8//
9// available at https://modern-c.appspot.com/-/builder/?importpath=modernc.org%2fmemory
10//
11// Changelog
12//
13// 2017-10-03 Added alternative, unsafe.Pointer-based API.
14//
15// Package memory implements a memory allocator.
16//
17// Changelog
18//
19// 2017-10-03 Added alternative, unsafe.Pointer-based API.
20//
21// Benchmarks
22//
23// AMD Ryzen 9 3900X 12-Core Processor × 24
24//
25// jnml@3900x:~/src/modernc.org/memory$ date ; go version ; go test -run @ -bench . -benchmem |& tee log
26// Fri Nov 20 17:23:04 CET 2020
27// go version go1.15.5 linux/amd64
28// goos: linux
29// goarch: amd64
30// pkg: modernc.org/memory
31// BenchmarkFree16-24 141188362 8.26 ns/op 0 B/op 0 allocs/op
32// BenchmarkFree32-24 100000000 11.4 ns/op 0 B/op 0 allocs/op
33// BenchmarkFree64-24 67160647 18.3 ns/op 0 B/op 0 allocs/op
34// BenchmarkCalloc16-24 60612698 19.8 ns/op 0 B/op 0 allocs/op
35// BenchmarkCalloc32-24 47968105 23.8 ns/op 0 B/op 0 allocs/op
36// BenchmarkCalloc64-24 40752181 28.6 ns/op 0 B/op 0 allocs/op
37// BenchmarkGoCalloc16-24 66487354 17.8 ns/op 16 B/op 1 allocs/op
38// BenchmarkGoCalloc32-24 56009206 21.2 ns/op 32 B/op 1 allocs/op
39// BenchmarkGoCalloc64-24 52086571 23.4 ns/op 64 B/op 1 allocs/op
40// BenchmarkMalloc16-24 113943390 10.2 ns/op 0 B/op 0 allocs/op
41// BenchmarkMalloc32-24 113520471 10.2 ns/op 0 B/op 0 allocs/op
42// BenchmarkMalloc64-24 108787056 10.7 ns/op 0 B/op 0 allocs/op
43// BenchmarkUintptrFree16-24 146110286 7.94 ns/op 0 B/op 0 allocs/op
44// BenchmarkUintptrFree32-24 93052707 12.0 ns/op 0 B/op 0 allocs/op
45// BenchmarkUintptrFree64-24 69805262 17.3 ns/op 0 B/op 0 allocs/op
46// BenchmarkUintptrCalloc16-24 85282725 13.7 ns/op 0 B/op 0 allocs/op
47// BenchmarkUintptrCalloc32-24 66489789 17.9 ns/op 0 B/op 0 allocs/op
48// BenchmarkUintptrCalloc64-24 53561092 22.7 ns/op 0 B/op 0 allocs/op
49// BenchmarkUintptrMalloc16-24 222978858 5.28 ns/op 0 B/op 0 allocs/op
50// BenchmarkUintptrMalloc32-24 210443384 5.30 ns/op 0 B/op 0 allocs/op
51// BenchmarkUintptrMalloc64-24 213706227 5.47 ns/op 0 B/op 0 allocs/op
52// PASS
53// ok modernc.org/memory 70.528s
54// jnml@3900x:~/src/modernc.org/memory$
55//
56// Intel® Core™ i5-4670 CPU @ 3.40GHz × 4
57//
58// ==== jnml@4670:~/src/modernc.org/memory> date ; go version ; go test -run @ -bench . -benchmem |& tee log
59// Sat Dec 8 12:56:53 CET 2018
60// go version go1.11.2 linux/amd64
61// goos: linux
62// goarch: amd64
63// pkg: modernc.org/memory
64// BenchmarkFree16-4 100000000 14.7 ns/op 0 B/op 0 allocs/op
65// BenchmarkFree32-4 100000000 20.5 ns/op 0 B/op 0 allocs/op
66// BenchmarkFree64-4 50000000 32.8 ns/op 0 B/op 0 allocs/op
67// BenchmarkCalloc16-4 50000000 24.4 ns/op 0 B/op 0 allocs/op
68// BenchmarkCalloc32-4 50000000 29.2 ns/op 0 B/op 0 allocs/op
69// BenchmarkCalloc64-4 50000000 35.7 ns/op 0 B/op 0 allocs/op
70// BenchmarkGoCalloc16-4 50000000 27.0 ns/op 16 B/op 1 allocs/op
71// BenchmarkGoCalloc32-4 50000000 27.3 ns/op 32 B/op 1 allocs/op
72// BenchmarkGoCalloc64-4 30000000 37.9 ns/op 64 B/op 1 allocs/op
73// BenchmarkMalloc16-4 100000000 12.9 ns/op 0 B/op 0 allocs/op
74// BenchmarkMalloc32-4 100000000 12.9 ns/op 0 B/op 0 allocs/op
75// BenchmarkMalloc64-4 100000000 13.2 ns/op 0 B/op 0 allocs/op
76// BenchmarkUintptrFree16-4 100000000 12.0 ns/op 0 B/op 0 allocs/op
77// BenchmarkUintptrFree32-4 100000000 17.5 ns/op 0 B/op 0 allocs/op
78// BenchmarkUintptrFree64-4 50000000 28.9 ns/op 0 B/op 0 allocs/op
79// BenchmarkUintptrCalloc16-4 100000000 17.8 ns/op 0 B/op 0 allocs/op
80// BenchmarkUintptrCalloc32-4 100000000 22.9 ns/op 0 B/op 0 allocs/op
81// BenchmarkUintptrCalloc64-4 50000000 29.6 ns/op 0 B/op 0 allocs/op
82// BenchmarkUintptrMalloc16-4 200000000 7.31 ns/op 0 B/op 0 allocs/op
83// BenchmarkUintptrMalloc32-4 200000000 7.47 ns/op 0 B/op 0 allocs/op
84// BenchmarkUintptrMalloc64-4 200000000 7.68 ns/op 0 B/op 0 allocs/op
85// PASS
86// ok modernc.org/memory 73.859s
87// //
88// Intel® Xeon(R) CPU E5-1650 v2 @ 3.50GHz × 12
89//
90// ==== jnml@e5-1650:~/src/modernc.org/memory> date ; go version ; go test -run @ -bench . -benchmem
91// Fri Dec 7 14:18:50 CET 2018
92// go version go1.11.2 linux/amd64
93// goos: linux
94// goarch: amd64
95// pkg: modernc.org/memory
96// BenchmarkFree16-12 100000000 16.7 ns/op 0 B/op 0 allocs/op
97// BenchmarkFree32-12 50000000 25.0 ns/op 0 B/op 0 allocs/op
98// BenchmarkFree64-12 30000000 39.7 ns/op 0 B/op 0 allocs/op
99// BenchmarkCalloc16-12 50000000 26.3 ns/op 0 B/op 0 allocs/op
100// BenchmarkCalloc32-12 50000000 33.4 ns/op 0 B/op 0 allocs/op
101// BenchmarkCalloc64-12 30000000 38.3 ns/op 0 B/op 0 allocs/op
102// BenchmarkGoCalloc16-12 50000000 26.6 ns/op 16 B/op 1 allocs/op
103// BenchmarkGoCalloc32-12 50000000 26.8 ns/op 32 B/op 1 allocs/op
104// BenchmarkGoCalloc64-12 30000000 35.1 ns/op 64 B/op 1 allocs/op
105// BenchmarkMalloc16-12 100000000 13.5 ns/op 0 B/op 0 allocs/op
106// BenchmarkMalloc32-12 100000000 13.4 ns/op 0 B/op 0 allocs/op
107// BenchmarkMalloc64-12 100000000 14.1 ns/op 0 B/op 0 allocs/op
108// BenchmarkUintptrFree16-12 100000000 14.4 ns/op 0 B/op 0 allocs/op
109// BenchmarkUintptrFree32-12 100000000 21.7 ns/op 0 B/op 0 allocs/op
110// BenchmarkUintptrFree64-12 50000000 36.7 ns/op 0 B/op 0 allocs/op
111// BenchmarkUintptrCalloc16-12 100000000 20.4 ns/op 0 B/op 0 allocs/op
112// BenchmarkUintptrCalloc32-12 50000000 27.1 ns/op 0 B/op 0 allocs/op
113// BenchmarkUintptrCalloc64-12 50000000 33.4 ns/op 0 B/op 0 allocs/op
114// BenchmarkUintptrMalloc16-12 200000000 8.02 ns/op 0 B/op 0 allocs/op
115// BenchmarkUintptrMalloc32-12 200000000 8.28 ns/op 0 B/op 0 allocs/op
116// BenchmarkUintptrMalloc64-12 200000000 8.29 ns/op 0 B/op 0 allocs/op
117// PASS
118// ok modernc.org/memory 80.896s
119package memory // import "modernc.org/memory"
120
121import (
122 "fmt"
123 "math/bits"
124 "os"
125 "reflect"
126 "unsafe"
127)
128
129const (
130 headerSize = unsafe.Sizeof(page{})
131 mallocAllign = 2 * unsafe.Sizeof(uintptr(0))
132 maxSlotSize = 1 << maxSlotSizeLog
133 maxSlotSizeLog = pageSizeLog - 2
134 pageAvail = pageSize - headerSize
135 pageMask = pageSize - 1
136 pageSize = 1 << pageSizeLog
137)
138
139func init() {
140 if unsafe.Sizeof(page{})%mallocAllign != 0 {
141 panic("internal error")
142 }
143}
144
145// if n%m != 0 { n += m-n%m }. m must be a power of 2.
146func roundup(n, m int) int { return (n + m - 1) &^ (m - 1) }
147
148type node struct {
149 prev, next uintptr // *node
150}
151
152type page struct {
153 brk int
154 log uint
155 size int
156 used int
157}
158
159// Allocator allocates and frees memory. Its zero value is ready for use. The
160// exported counters are updated only when build tag memory.counters is
161// present.
162type Allocator struct {
163 Allocs int // # of allocs.
164 Bytes int // Asked from OS.
165 cap [64]int
166 lists [64]uintptr // *node
167 Mmaps int // Asked from OS.
168 pages [64]uintptr // *page
169 regs map[uintptr]struct{} // map[*page]struct{}
170}
171
172func (a *Allocator) mmap(size int) (uintptr /* *page */, error) {
173 p, size, err := mmap(size)
174 if err != nil {
175 return 0, err
176 }
177
178 if counters {
179 a.Mmaps++
180 a.Bytes += size
181 }
182 if a.regs == nil {
183 a.regs = map[uintptr]struct{}{}
184 }
185 (*page)(unsafe.Pointer(p)).size = size
186 a.regs[p] = struct{}{}
187 return p, nil
188}
189
190func (a *Allocator) newPage(size int) (uintptr /* *page */, error) {
191 size += int(headerSize)
192 p, err := a.mmap(size)
193 if err != nil {
194 return 0, err
195 }
196
197 (*page)(unsafe.Pointer(p)).log = 0
198 return p, nil
199}
200
201func (a *Allocator) newSharedPage(log uint) (uintptr /* *page */, error) {
202 if a.cap[log] == 0 {
203 a.cap[log] = int(pageAvail) / (1 << log)
204 }
205 size := int(headerSize) + a.cap[log]<<log
206 p, err := a.mmap(size)
207 if err != nil {
208 return 0, err
209 }
210
211 a.pages[log] = p
212 (*page)(unsafe.Pointer(p)).log = log
213 return p, nil
214}
215
216func (a *Allocator) unmap(p uintptr /* *page */) error {
217 delete(a.regs, p)
218 if counters {
219 a.Mmaps--
220 }
221 return unmap(p, (*page)(unsafe.Pointer(p)).size)
222}
223
224// UintptrCalloc is like Calloc except it returns an uintptr.
225func (a *Allocator) UintptrCalloc(size int) (r uintptr, err error) {
226 if trace {
227 defer func() {
228 fmt.Fprintf(os.Stderr, "Calloc(%#x) %#x, %v\n", size, r, err)
229 }()
230 }
231 if r, err = a.UintptrMalloc(size); r == 0 || err != nil {
232 return 0, err
233 }
234 b := ((*rawmem)(unsafe.Pointer(r)))[:size:size]
235 for i := range b {
236 b[i] = 0
237 }
238 return r, nil
239}
240
241// UintptrFree is like Free except its argument is an uintptr, which must have
242// been acquired from UintptrCalloc or UintptrMalloc or UintptrRealloc.
243func (a *Allocator) UintptrFree(p uintptr) (err error) {
244 if trace {
245 defer func() {
246 fmt.Fprintf(os.Stderr, "Free(%#x) %v\n", p, err)
247 }()
248 }
249 if p == 0 {
250 return nil
251 }
252
253 if counters {
254 a.Allocs--
255 }
256 pg := p &^ uintptr(pageMask)
257 log := (*page)(unsafe.Pointer(pg)).log
258 if log == 0 {
259 if counters {
260 a.Bytes -= (*page)(unsafe.Pointer(pg)).size
261 }
262 return a.unmap(pg)
263 }
264
265 (*node)(unsafe.Pointer(p)).prev = 0
266 (*node)(unsafe.Pointer(p)).next = a.lists[log]
267 if next := (*node)(unsafe.Pointer(p)).next; next != 0 {
268 (*node)(unsafe.Pointer(next)).prev = p
269 }
270 a.lists[log] = p
271 (*page)(unsafe.Pointer(pg)).used--
272 if (*page)(unsafe.Pointer(pg)).used != 0 {
273 return nil
274 }
275
276 for i := 0; i < (*page)(unsafe.Pointer(pg)).brk; i++ {
277 n := pg + headerSize + uintptr(i)<<log
278 next := (*node)(unsafe.Pointer(n)).next
279 prev := (*node)(unsafe.Pointer(n)).prev
280 switch {
281 case prev == 0:
282 a.lists[log] = next
283 if next != 0 {
284 (*node)(unsafe.Pointer(next)).prev = 0
285 }
286 case next == 0:
287 (*node)(unsafe.Pointer(prev)).next = 0
288 default:
289 (*node)(unsafe.Pointer(prev)).next = next
290 (*node)(unsafe.Pointer(next)).prev = prev
291 }
292 }
293
294 if a.pages[log] == pg {
295 a.pages[log] = 0
296 }
297 if counters {
298 a.Bytes -= (*page)(unsafe.Pointer(pg)).size
299 }
300 return a.unmap(pg)
301}
302
303// UintptrMalloc is like Malloc except it returns an uinptr.
304func (a *Allocator) UintptrMalloc(size int) (r uintptr, err error) {
305 if trace {
306 defer func() {
307 fmt.Fprintf(os.Stderr, "Malloc(%#x) %#x, %v\n", size, r, err)
308 }()
309 }
310 if size < 0 {
311 panic("invalid malloc size")
312 }
313
314 if size == 0 {
315 return 0, nil
316 }
317
318 if counters {
319 a.Allocs++
320 }
321 log := uint(bits.Len(uint((size+int(mallocAllign)-1)&^int(mallocAllign-1) - 1)))
322 if log > maxSlotSizeLog {
323 p, err := a.newPage(size)
324 if err != nil {
325 return 0, err
326 }
327
328 return p + headerSize, nil
329 }
330
331 if a.lists[log] == 0 && a.pages[log] == 0 {
332 if _, err := a.newSharedPage(log); err != nil {
333 return 0, err
334 }
335 }
336
337 if p := a.pages[log]; p != 0 {
338 (*page)(unsafe.Pointer(p)).used++
339 (*page)(unsafe.Pointer(p)).brk++
340 if (*page)(unsafe.Pointer(p)).brk == a.cap[log] {
341 a.pages[log] = 0
342 }
343 return p + headerSize + uintptr((*page)(unsafe.Pointer(p)).brk-1)<<log, nil
344 }
345
346 n := a.lists[log]
347 p := n &^ uintptr(pageMask)
348 a.lists[log] = (*node)(unsafe.Pointer(n)).next
349 if next := (*node)(unsafe.Pointer(n)).next; next != 0 {
350 (*node)(unsafe.Pointer(next)).prev = 0
351 }
352 (*page)(unsafe.Pointer(p)).used++
353 return n, nil
354}
355
356// UintptrRealloc is like Realloc except its first argument is an uintptr,
357// which must have been returned from UintptrCalloc, UintptrMalloc or
358// UintptrRealloc.
359func (a *Allocator) UintptrRealloc(p uintptr, size int) (r uintptr, err error) {
360 if trace {
361 defer func() {
362 fmt.Fprintf(os.Stderr, "UnsafeRealloc(%#x, %#x) %#x, %v\n", p, size, r, err)
363 }()
364 }
365 switch {
366 case p == 0:
367 return a.UintptrMalloc(size)
368 case size == 0 && p != 0:
369 return 0, a.UintptrFree(p)
370 }
371
372 us := UintptrUsableSize(p)
373 if us > size {
374 return p, nil
375 }
376
377 if r, err = a.UintptrMalloc(size); err != nil {
378 return 0, err
379 }
380
381 if us < size {
382 size = us
383 }
384 copy((*rawmem)(unsafe.Pointer(r))[:size:size], (*rawmem)(unsafe.Pointer(p))[:size:size])
385 return r, a.UintptrFree(p)
386}
387
388// UintptrUsableSize is like UsableSize except its argument is an uintptr,
389// which must have been returned from UintptrCalloc, UintptrMalloc or
390// UintptrRealloc.
391func UintptrUsableSize(p uintptr) (r int) {
392 if trace {
393 defer func() {
394 fmt.Fprintf(os.Stderr, "UsableSize(%#x) %#x\n", p, r)
395 }()
396 }
397 if p == 0 {
398 return 0
399 }
400
401 return usableSize(p)
402}
403
404func usableSize(p uintptr) (r int) {
405 pg := p &^ uintptr(pageMask)
406 if log := (*page)(unsafe.Pointer(pg)).log; log != 0 {
407 return 1 << log
408 }
409
410 return (*page)(unsafe.Pointer(pg)).size - int(headerSize)
411}
412
413// Calloc is like Malloc except the allocated memory is zeroed.
414func (a *Allocator) Calloc(size int) (r []byte, err error) {
415 p, err := a.UintptrCalloc(size)
416 if err != nil {
417 return nil, err
418 }
419
420 var b []byte
421 sh := (*reflect.SliceHeader)(unsafe.Pointer(&b))
422 sh.Cap = usableSize(p)
423 sh.Data = p
424 sh.Len = size
425 return b, nil
426}
427
428// Close releases all OS resources used by a and sets it to its zero value.
429//
430// It's not necessary to Close the Allocator when exiting a process.
431func (a *Allocator) Close() (err error) {
432 for p := range a.regs {
433 if e := a.unmap(p); e != nil && err == nil {
434 err = e
435 }
436 }
437 *a = Allocator{}
438 return err
439}
440
441// Free deallocates memory (as in C.free). The argument of Free must have been
442// acquired from Calloc or Malloc or Realloc.
443func (a *Allocator) Free(b []byte) (err error) {
444 if b = b[:cap(b)]; len(b) == 0 {
445 return nil
446 }
447
448 return a.UintptrFree(uintptr(unsafe.Pointer(&b[0])))
449}
450
451// Malloc allocates size bytes and returns a byte slice of the allocated
452// memory. The memory is not initialized. Malloc panics for size < 0 and
453// returns (nil, nil) for zero size.
454//
455// It's ok to reslice the returned slice but the result of appending to it
456// cannot be passed to Free or Realloc as it may refer to a different backing
457// array afterwards.
458func (a *Allocator) Malloc(size int) (r []byte, err error) {
459 p, err := a.UintptrMalloc(size)
460 if p == 0 || err != nil {
461 return nil, err
462 }
463
464 sh := (*reflect.SliceHeader)(unsafe.Pointer(&r))
465 sh.Cap = usableSize(p)
466 sh.Data = p
467 sh.Len = size
468 return r, nil
469}
470
471// Realloc changes the size of the backing array of b to size bytes or returns
472// an error, if any. The contents will be unchanged in the range from the
473// start of the region up to the minimum of the old and new sizes. If the
474// new size is larger than the old size, the added memory will not be
475// initialized. If b's backing array is of zero size, then the call is
476// equivalent to Malloc(size), for all values of size; if size is equal to
477// zero, and b's backing array is not of zero size, then the call is equivalent
478// to Free(b). Unless b's backing array is of zero size, it must have been
479// returned by an earlier call to Malloc, Calloc or Realloc. If the area
480// pointed to was moved, a Free(b) is done.
481func (a *Allocator) Realloc(b []byte, size int) (r []byte, err error) {
482 var p uintptr
483 if b = b[:cap(b)]; len(b) != 0 {
484 p = uintptr(unsafe.Pointer(&b[0]))
485 }
486 if p, err = a.UintptrRealloc(p, size); p == 0 || err != nil {
487 return nil, err
488 }
489
490 sh := (*reflect.SliceHeader)(unsafe.Pointer(&r))
491 sh.Cap = usableSize(p)
492 sh.Data = p
493 sh.Len = size
494 return r, nil
495}
496
497// UsableSize reports the size of the memory block allocated at p, which must
498// point to the first byte of a slice returned from Calloc, Malloc or Realloc.
499// The allocated memory block size can be larger than the size originally
500// requested from Calloc, Malloc or Realloc.
501func UsableSize(p *byte) (r int) { return UintptrUsableSize(uintptr(unsafe.Pointer(p))) }
502
503// UnsafeCalloc is like Calloc except it returns an unsafe.Pointer.
504func (a *Allocator) UnsafeCalloc(size int) (r unsafe.Pointer, err error) {
505 p, err := a.UintptrCalloc(size)
506 if err != nil {
507 return nil, err
508 }
509
510 return unsafe.Pointer(p), nil
511}
512
513// UnsafeFree is like Free except its argument is an unsafe.Pointer, which must
514// have been acquired from UnsafeCalloc or UnsafeMalloc or UnsafeRealloc.
515func (a *Allocator) UnsafeFree(p unsafe.Pointer) (err error) { return a.UintptrFree(uintptr(p)) }
516
517// UnsafeMalloc is like Malloc except it returns an unsafe.Pointer.
518func (a *Allocator) UnsafeMalloc(size int) (r unsafe.Pointer, err error) {
519 p, err := a.UintptrMalloc(size)
520 if err != nil {
521 return nil, err
522 }
523
524 return unsafe.Pointer(p), nil
525}
526
527// UnsafeRealloc is like Realloc except its first argument is an
528// unsafe.Pointer, which must have been returned from UnsafeCalloc,
529// UnsafeMalloc or UnsafeRealloc.
530func (a *Allocator) UnsafeRealloc(p unsafe.Pointer, size int) (r unsafe.Pointer, err error) {
531 q, err := a.UintptrRealloc(uintptr(p), size)
532 if err != nil {
533 return nil, err
534 }
535
536 return unsafe.Pointer(q), nil
537}
538
539// UnsafeUsableSize is like UsableSize except its argument is an
540// unsafe.Pointer, which must have been returned from UnsafeCalloc,
541// UnsafeMalloc or UnsafeRealloc.
542func UnsafeUsableSize(p unsafe.Pointer) (r int) { return UintptrUsableSize(uintptr(p)) }
Note: See TracBrowser for help on using the repository browser.