freelist_hmap.go

Documentation: go.etcd.io/bbolt

     1  package bbolt
     2  
     3  import "sort"
     4  
     5  // hashmapFreeCount returns count of free pages(hashmap version)
     6  func (f *freelist) hashmapFreeCount() int {
     7  	// use the forwardMap to get the total count
     8  	count := 0
     9  	for _, size := range f.forwardMap {
    10  		count += int(size)
    11  	}
    12  	return count
    13  }
    14  
    15  // hashmapAllocate serves the same purpose as arrayAllocate, but use hashmap as backend
    16  func (f *freelist) hashmapAllocate(txid txid, n int) pgid {
    17  	if n == 0 {
    18  		return 0
    19  	}
    20  
    21  	// if we have a exact size match just return short path
    22  	if bm, ok := f.freemaps[uint64(n)]; ok {
    23  		for pid := range bm {
    24  			// remove the span
    25  			f.delSpan(pid, uint64(n))
    26  
    27  			f.allocs[pid] = txid
    28  
    29  			for i := pgid(0); i < pgid(n); i++ {
    30  				delete(f.cache, pid+i)
    31  			}
    32  			return pid
    33  		}
    34  	}
    35  
    36  	// lookup the map to find larger span
    37  	for size, bm := range f.freemaps {
    38  		if size < uint64(n) {
    39  			continue
    40  		}
    41  
    42  		for pid := range bm {
    43  			// remove the initial
    44  			f.delSpan(pid, size)
    45  
    46  			f.allocs[pid] = txid
    47  
    48  			remain := size - uint64(n)
    49  
    50  			// add remain span
    51  			f.addSpan(pid+pgid(n), remain)
    52  
    53  			for i := pgid(0); i < pgid(n); i++ {
    54  				delete(f.cache, pid+i)
    55  			}
    56  			return pid
    57  		}
    58  	}
    59  
    60  	return 0
    61  }
    62  
    63  // hashmapReadIDs reads pgids as input an initial the freelist(hashmap version)
    64  func (f *freelist) hashmapReadIDs(pgids []pgid) {
    65  	f.init(pgids)
    66  
    67  	// Rebuild the page cache.
    68  	f.reindex()
    69  }
    70  
    71  // hashmapGetFreePageIDs returns the sorted free page ids
    72  func (f *freelist) hashmapGetFreePageIDs() []pgid {
    73  	count := f.free_count()
    74  	if count == 0 {
    75  		return nil
    76  	}
    77  
    78  	m := make([]pgid, 0, count)
    79  	for start, size := range f.forwardMap {
    80  		for i := 0; i < int(size); i++ {
    81  			m = append(m, start+pgid(i))
    82  		}
    83  	}
    84  	sort.Sort(pgids(m))
    85  
    86  	return m
    87  }
    88  
    89  // hashmapMergeSpans try to merge list of pages(represented by pgids) with existing spans
    90  func (f *freelist) hashmapMergeSpans(ids pgids) {
    91  	for _, id := range ids {
    92  		// try to see if we can merge and update
    93  		f.mergeWithExistingSpan(id)
    94  	}
    95  }
    96  
    97  // mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward
    98  func (f *freelist) mergeWithExistingSpan(pid pgid) {
    99  	prev := pid - 1
   100  	next := pid + 1
   101  
   102  	preSize, mergeWithPrev := f.backwardMap[prev]
   103  	nextSize, mergeWithNext := f.forwardMap[next]
   104  	newStart := pid
   105  	newSize := uint64(1)
   106  
   107  	if mergeWithPrev {
   108  		//merge with previous span
   109  		start := prev + 1 - pgid(preSize)
   110  		f.delSpan(start, preSize)
   111  
   112  		newStart -= pgid(preSize)
   113  		newSize += preSize
   114  	}
   115  
   116  	if mergeWithNext {
   117  		// merge with next span
   118  		f.delSpan(next, nextSize)
   119  		newSize += nextSize
   120  	}
   121  
   122  	f.addSpan(newStart, newSize)
   123  }
   124  
   125  func (f *freelist) addSpan(start pgid, size uint64) {
   126  	f.backwardMap[start-1+pgid(size)] = size
   127  	f.forwardMap[start] = size
   128  	if _, ok := f.freemaps[size]; !ok {
   129  		f.freemaps[size] = make(map[pgid]struct{})
   130  	}
   131  
   132  	f.freemaps[size][start] = struct{}{}
   133  }
   134  
   135  func (f *freelist) delSpan(start pgid, size uint64) {
   136  	delete(f.forwardMap, start)
   137  	delete(f.backwardMap, start+pgid(size-1))
   138  	delete(f.freemaps[size], start)
   139  	if len(f.freemaps[size]) == 0 {
   140  		delete(f.freemaps, size)
   141  	}
   142  }
   143  
   144  // initial from pgids using when use hashmap version
   145  // pgids must be sorted
   146  func (f *freelist) init(pgids []pgid) {
   147  	if len(pgids) == 0 {
   148  		return
   149  	}
   150  
   151  	size := uint64(1)
   152  	start := pgids[0]
   153  
   154  	if !sort.SliceIsSorted([]pgid(pgids), func(i, j int) bool { return pgids[i] < pgids[j] }) {
   155  		panic("pgids not sorted")
   156  	}
   157  
   158  	f.freemaps = make(map[uint64]pidSet)
   159  	f.forwardMap = make(map[pgid]uint64)
   160  	f.backwardMap = make(map[pgid]uint64)
   161  
   162  	for i := 1; i < len(pgids); i++ {
   163  		// continuous page
   164  		if pgids[i] == pgids[i-1]+1 {
   165  			size++
   166  		} else {
   167  			f.addSpan(start, size)
   168  
   169  			size = 1
   170  			start = pgids[i]
   171  		}
   172  	}
   173  
   174  	// init the tail
   175  	if size != 0 && start != 0 {
   176  		f.addSpan(start, size)
   177  	}
   178  }
   179
View as plain text