This repository has been archived by the owner on Feb 12, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 9
/
sequence.go
454 lines (397 loc) · 12.1 KB
/
sequence.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
// Package bitseq provides a structure and utilities for representing long bitmask
// as sequence of run-lenght encoded blocks. It operates direclty on the encoded
// representation, it does not decode/encode.
package bitseq
import (
"fmt"
"sync"
"github.com/docker/libnetwork/datastore"
"github.com/docker/libnetwork/netutils"
)
// Block Sequence constants
// If needed we can think of making these configurable
const (
blockLen = 32
blockBytes = blockLen / 8
blockMAX = 1<<blockLen - 1
blockFirstBit = 1 << (blockLen - 1)
)
// Handle contains the sequece representing the bitmask and its identifier
type Handle struct {
bits uint32
unselected uint32
head *Sequence
app string
id string
dbIndex uint64
dbExists bool
store datastore.DataStore
sync.Mutex
}
// NewHandle returns a thread-safe instance of the bitmask handler
func NewHandle(app string, ds datastore.DataStore, id string, numElements uint32) (*Handle, error) {
h := &Handle{
app: app,
id: id,
store: ds,
bits: numElements,
unselected: numElements,
head: &Sequence{
Block: 0x0,
Count: getNumBlocks(numElements),
},
}
if h.store == nil {
return h, nil
}
// Register for status changes
h.watchForChanges()
// Get the initial status from the ds if present.
if err := h.store.GetObject(datastore.Key(h.Key()...), h); err != nil && err != datastore.ErrKeyNotFound {
return nil, err
}
return h, nil
}
// Sequence reresents a recurring sequence of 32 bits long bitmasks
type Sequence struct {
Block uint32 // block representing 4 byte long allocation bitmask
Count uint32 // number of consecutive blocks
Next *Sequence // next sequence
}
// NewSequence returns a sequence initialized to represent a bitmaks of numElements bits
func NewSequence(numElements uint32) *Sequence {
return &Sequence{Block: 0x0, Count: getNumBlocks(numElements), Next: nil}
}
// String returns a string representation of the block sequence starting from this block
func (s *Sequence) String() string {
var nextBlock string
if s.Next == nil {
nextBlock = "end"
} else {
nextBlock = s.Next.String()
}
return fmt.Sprintf("(0x%x, %d)->%s", s.Block, s.Count, nextBlock)
}
// GetAvailableBit returns the position of the first unset bit in the bitmask represented by this sequence
func (s *Sequence) GetAvailableBit() (bytePos, bitPos int) {
if s.Block == blockMAX || s.Count == 0 {
return -1, -1
}
bits := 0
bitSel := uint32(blockFirstBit)
for bitSel > 0 && s.Block&bitSel != 0 {
bitSel >>= 1
bits++
}
return bits / 8, bits % 8
}
// GetCopy returns a copy of the linked list rooted at this node
func (s *Sequence) GetCopy() *Sequence {
n := &Sequence{Block: s.Block, Count: s.Count}
pn := n
ps := s.Next
for ps != nil {
pn.Next = &Sequence{Block: ps.Block, Count: ps.Count}
pn = pn.Next
ps = ps.Next
}
return n
}
// Equal checks if this sequence is equal to the passed one
func (s *Sequence) Equal(o *Sequence) bool {
this := s
other := o
for this != nil {
if other == nil {
return false
}
if this.Block != other.Block || this.Count != other.Count {
return false
}
this = this.Next
other = other.Next
}
// Check if other is longer than this
if other != nil {
return false
}
return true
}
// ToByteArray converts the sequence into a byte array
// TODO (aboch): manage network/host order stuff
func (s *Sequence) ToByteArray() ([]byte, error) {
var bb []byte
p := s
for p != nil {
bb = append(bb, netutils.U32ToA(p.Block)...)
bb = append(bb, netutils.U32ToA(p.Count)...)
p = p.Next
}
return bb, nil
}
// FromByteArray construct the sequence from the byte array
// TODO (aboch): manage network/host order stuff
func (s *Sequence) FromByteArray(data []byte) error {
l := len(data)
if l%8 != 0 {
return fmt.Errorf("cannot deserialize byte sequence of lenght %d (%v)", l, data)
}
p := s
i := 0
for {
p.Block = netutils.ATo32(data[i : i+4])
p.Count = netutils.ATo32(data[i+4 : i+8])
i += 8
if i == l {
break
}
p.Next = &Sequence{}
p = p.Next
}
return nil
}
// GetFirstAvailable returns the byte and bit position of the first unset bit
func (h *Handle) GetFirstAvailable() (int, int, error) {
h.Lock()
defer h.Unlock()
return GetFirstAvailable(h.head)
}
// CheckIfAvailable checks if the bit correspondent to the specified ordinal is unset
// If the ordinal is beyond the Sequence limits, a negative response is returned
func (h *Handle) CheckIfAvailable(ordinal int) (int, int, error) {
h.Lock()
defer h.Unlock()
return CheckIfAvailable(h.head, ordinal)
}
// PushReservation pushes the bit reservation inside the bitmask.
func (h *Handle) PushReservation(bytePos, bitPos int, release bool) error {
// Create a copy of the current handler
h.Lock()
nh := &Handle{
app: h.app,
id: h.id,
store: h.store,
dbIndex: h.dbIndex,
head: h.head.GetCopy(),
dbExists: h.dbExists,
}
h.Unlock()
nh.head = PushReservation(bytePos, bitPos, nh.head, release)
err := nh.writeToStore()
if err == nil {
// Commit went through, save locally
h.Lock()
h.head = nh.head
if release {
h.unselected++
} else {
h.unselected--
}
// Can't use SetIndex() since we're locked.
h.dbIndex = nh.Index()
h.dbExists = true
h.Unlock()
}
return err
}
// Destroy removes from the datastore the data belonging to this handle
func (h *Handle) Destroy() {
h.deleteFromStore()
}
// ToByteArray converts this handle's data into a byte array
func (h *Handle) ToByteArray() ([]byte, error) {
ba := make([]byte, 8)
h.Lock()
defer h.Unlock()
copy(ba[0:4], netutils.U32ToA(h.bits))
copy(ba[4:8], netutils.U32ToA(h.unselected))
bm, err := h.head.ToByteArray()
if err != nil {
return nil, fmt.Errorf("failed to serialize head: %s", err.Error())
}
ba = append(ba, bm...)
return ba, nil
}
// FromByteArray reads his handle's data from a byte array
func (h *Handle) FromByteArray(ba []byte) error {
if ba == nil {
return fmt.Errorf("nil byte array")
}
nh := &Sequence{}
err := nh.FromByteArray(ba[8:])
if err != nil {
return fmt.Errorf("failed to deserialize head: %s", err.Error())
}
h.Lock()
h.head = nh
h.bits = netutils.ATo32(ba[0:4])
h.unselected = netutils.ATo32(ba[4:8])
h.Unlock()
return nil
}
// Bits returns the length of the bit sequence
func (h *Handle) Bits() uint32 {
return h.bits
}
// Unselected returns the number of bits which are not selected
func (h *Handle) Unselected() uint32 {
h.Lock()
defer h.Unlock()
return h.unselected
}
// GetFirstAvailable looks for the first unset bit in passed mask
func GetFirstAvailable(head *Sequence) (int, int, error) {
byteIndex := 0
current := head
for current != nil {
if current.Block != blockMAX {
bytePos, bitPos := current.GetAvailableBit()
return byteIndex + bytePos, bitPos, nil
}
byteIndex += int(current.Count * blockBytes)
current = current.Next
}
return -1, -1, fmt.Errorf("no bit available")
}
// CheckIfAvailable checks if the bit correspondent to the specified ordinal is unset
// If the ordinal is beyond the Sequence limits, a negative response is returned
func CheckIfAvailable(head *Sequence, ordinal int) (int, int, error) {
bytePos := ordinal / 8
bitPos := ordinal % 8
// Find the Sequence containing this byte
current, _, _, inBlockBytePos := findSequence(head, bytePos)
if current != nil {
// Check whether the bit corresponding to the ordinal address is unset
bitSel := uint32(blockFirstBit >> uint(inBlockBytePos*8+bitPos))
if current.Block&bitSel == 0 {
return bytePos, bitPos, nil
}
}
return -1, -1, fmt.Errorf("requested bit is not available")
}
// Given the byte position and the sequences list head, return the pointer to the
// sequence containing the byte (current), the pointer to the previous sequence,
// the number of blocks preceding the block containing the byte inside the current sequence.
// If bytePos is outside of the list, function will return (nil, nil, 0, -1)
func findSequence(head *Sequence, bytePos int) (*Sequence, *Sequence, uint32, int) {
// Find the Sequence containing this byte
previous := head
current := head
n := bytePos
for current.Next != nil && n >= int(current.Count*blockBytes) { // Nil check for less than 32 addresses masks
n -= int(current.Count * blockBytes)
previous = current
current = current.Next
}
// If byte is outside of the list, let caller know
if n >= int(current.Count*blockBytes) {
return nil, nil, 0, -1
}
// Find the byte position inside the block and the number of blocks
// preceding the block containing the byte inside this sequence
precBlocks := uint32(n / blockBytes)
inBlockBytePos := bytePos % blockBytes
return current, previous, precBlocks, inBlockBytePos
}
// PushReservation pushes the bit reservation inside the bitmask.
// Given byte and bit positions, identify the sequence (current) which holds the block containing the affected bit.
// Create a new block with the modified bit according to the operation (allocate/release).
// Create a new Sequence containing the new Block and insert it in the proper position.
// Remove current sequence if empty.
// Check if new Sequence can be merged with neighbour (previous/Next) sequences.
//
//
// Identify "current" Sequence containing block:
// [prev seq] [current seq] [Next seq]
//
// Based on block position, resulting list of sequences can be any of three forms:
//
// Block position Resulting list of sequences
// A) Block is first in current: [prev seq] [new] [modified current seq] [Next seq]
// B) Block is last in current: [prev seq] [modified current seq] [new] [Next seq]
// C) Block is in the middle of current: [prev seq] [curr pre] [new] [curr post] [Next seq]
func PushReservation(bytePos, bitPos int, head *Sequence, release bool) *Sequence {
// Store list's head
newHead := head
// Find the Sequence containing this byte
current, previous, precBlocks, inBlockBytePos := findSequence(head, bytePos)
if current == nil {
return newHead
}
// Construct updated block
bitSel := uint32(blockFirstBit >> uint(inBlockBytePos*8+bitPos))
newBlock := current.Block
if release {
newBlock &^= bitSel
} else {
newBlock |= bitSel
}
// Quit if it was a redundant request
if current.Block == newBlock {
return newHead
}
// Current Sequence inevitably looses one block, upadate Count
current.Count--
// Create new sequence
newSequence := &Sequence{Block: newBlock, Count: 1}
// Insert the new sequence in the list based on block position
if precBlocks == 0 { // First in sequence (A)
newSequence.Next = current
if current == head {
newHead = newSequence
previous = newHead
} else {
previous.Next = newSequence
}
removeCurrentIfEmpty(&newHead, newSequence, current)
mergeSequences(previous)
} else if precBlocks == current.Count-2 { // Last in sequence (B)
newSequence.Next = current.Next
current.Next = newSequence
mergeSequences(current)
} else { // In between the sequence (C)
currPre := &Sequence{Block: current.Block, Count: precBlocks, Next: newSequence}
currPost := current
currPost.Count -= precBlocks
newSequence.Next = currPost
if currPost == head {
newHead = currPre
} else {
previous.Next = currPre
}
// No merging or empty current possible here
}
return newHead
}
// Removes the current sequence from the list if empty, adjusting the head pointer if needed
func removeCurrentIfEmpty(head **Sequence, previous, current *Sequence) {
if current.Count == 0 {
if current == *head {
*head = current.Next
} else {
previous.Next = current.Next
current = current.Next
}
}
}
// Given a pointer to a Sequence, it checks if it can be merged with any following sequences
// It stops when no more merging is possible.
// TODO: Optimization: only attempt merge from start to end sequence, no need to scan till the end of the list
func mergeSequences(seq *Sequence) {
if seq != nil {
// Merge all what possible from seq
for seq.Next != nil && seq.Block == seq.Next.Block {
seq.Count += seq.Next.Count
seq.Next = seq.Next.Next
}
// Move to Next
mergeSequences(seq.Next)
}
}
func getNumBlocks(numBits uint32) uint32 {
numBlocks := numBits / blockLen
if numBits%blockLen != 0 {
numBlocks++
}
return numBlocks
}