forked from knqyf263/go-rpmdb
/
hash_page.go
119 lines (96 loc) · 3.84 KB
/
hash_page.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
package bdb
import (
"encoding/binary"
"fmt"
"github.com/go-restruct/restruct"
"io"
"os"
)
// source: https://github.com/berkeleydb/libdb/blob/5b7b02ae052442626af54c176335b67ecc613a30/src/dbinc/db_page.h#L259
type HashPage struct {
LSN [8]byte `struct:"[8]byte"` /* 00-07: LSN. */
PageNo uint32 `struct:"uint32"` /* 08-11: Current page number. */
PreviousPageNo uint32 `struct:"uint32"` /* 12-15: Previous page number. */
NextPageNo uint32 `struct:"uint32"` /* 16-19: Next page number. */
NumEntries uint16 `struct:"uint16"` /* 20-21: Number of items on the page. */
FreeAreaOffset uint16 `struct:"uint16"` /* 22-23: High free byte page offset. */
TreeLevel uint8 `struct:"uint8"` /* 24: Btree tree level. */
PageType uint8 `struct:"uint8"` /* 25: Page type. */
}
func ParseHashPage(data []byte) (*HashPage, error) {
var hashPage HashPage
err := restruct.Unpack(data, binary.LittleEndian, &hashPage)
if err != nil {
return nil, fmt.Errorf("failed to unpack: %w", err)
}
return &hashPage, nil
}
func HashPageValueContent(db *os.File, pageData []byte, hashPageIndex uint16, pageSize uint32) ([]byte, error) {
// the first byte is the page type, so we can peek at it first before parsing further...
valuePageType := pageData[hashPageIndex]
// only HOFFPAGE page types have data of interest
if valuePageType != HashOffIndexPageType {
return nil, fmt.Errorf("only HOFFPAGE types supported (%+v)", valuePageType)
}
hashOffPageEntryBuff := pageData[hashPageIndex : hashPageIndex+HashOffPageSize]
entry, err := ParseHashOffPageEntry(hashOffPageEntryBuff)
if err != nil {
return nil, err
}
var hashValue []byte
for currentPageNo := entry.PageNo; currentPageNo != 0; {
pageStart := pageSize * currentPageNo
_, err := db.Seek(int64(pageStart), io.SeekStart)
if err != nil {
return nil, fmt.Errorf("failed to seek to HashPageValueContent (page=%d): %w", currentPageNo, err)
}
currentPageBuff, err := slice(db, int(pageSize))
if err != nil {
return nil, fmt.Errorf("failed to read page=%d: %w", currentPageNo, err)
}
currentPage, err := ParseHashPage(currentPageBuff)
if err != nil {
return nil, fmt.Errorf("failed to parse page=%d: %w", currentPageNo, err)
}
var hashValueBytes []byte
if currentPage.NextPageNo == 0 {
// this is the last page, the whole page contains content
hashValueBytes = currentPageBuff[PageHeaderSize : PageHeaderSize+currentPage.FreeAreaOffset]
} else {
hashValueBytes = currentPageBuff[PageHeaderSize:]
}
hashValue = append(hashValue, hashValueBytes...)
currentPageNo = currentPage.NextPageNo
}
return hashValue, nil
}
func HashPageValueIndexes(data []byte, entries uint16) ([]uint16, error) {
var hashIndexValues = make([]uint16, 0)
if entries%2 != 0 {
return nil, fmt.Errorf("invalid hash index: entries should only come in pairs (%+v)", entries)
}
// Every entry is a 2-byte offset that points somewhere in the current database page.
hashIndexSize := entries * HashIndexEntrySize
hashIndexData := data[PageHeaderSize : PageHeaderSize+hashIndexSize]
// data is stored in key-value pairs (https://github.com/berkeleydb/libdb/blob/5b7b02ae052442626af54c176335b67ecc613a30/src/dbinc/db_page.h#L591)
// skip over keys and only keep values
const keyValuePairSize = 2 * HashIndexEntrySize
for idx := range hashIndexData {
if (idx-HashIndexEntrySize)%keyValuePairSize == 0 {
value := binary.LittleEndian.Uint16(hashIndexData[idx : idx+2])
hashIndexValues = append(hashIndexValues, value)
}
}
return hashIndexValues, nil
}
func slice(reader io.Reader, n int) ([]byte, error) {
newBuff := make([]byte, n)
numRead, err := reader.Read(newBuff)
if err != nil {
return nil, fmt.Errorf("failed to read page: %w", err)
}
if numRead != n {
return nil, fmt.Errorf("short page size: %d!=%d", n, numRead)
}
return newBuff, nil
}