1 // Copyright 2019 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #pragma once
6
7 #include "limits.h"
8
9 #include <fbl/function.h>
10 #include <fbl/string.h>
11 #include <fbl/string_piece.h>
12 #include <fbl/type_support.h>
13
14 #include <zircon/types.h>
15
16 namespace inspect {
17
18 enum class BlockType {
19 kFree = 0,
20 kReserved = 1,
21 kHeader = 2,
22 kObjectValue = 3,
23 kIntValue = 4,
24 kUintValue = 5,
25 kDoubleValue = 6,
26 kStringValue = 7,
27 kExtent = 8,
28 kName = 9,
29 kTombstone = 10
30 };
31
32 namespace internal {
33
34 using BlockOrder = uint32_t;
35 using BlockIndex = uint64_t;
36
37 // Returns the smallest order such that (kMinOrderSize << order) >= size.
38 // Size must be non-zero.
FitOrder(size_t size)39 constexpr BlockOrder FitOrder(size_t size) {
40 auto ret = 64 - __builtin_clzl(size - 1) - kMinOrderShift;
41 return static_cast<BlockOrder>(ret);
42 }
43
44 // Structure of the block header and payload.
45 struct Block {
46 union {
47 uint64_t header;
48 char header_data[8];
49 };
50 union {
51 int64_t i64;
52 uint64_t u64;
53 double f64;
54 char data[8];
55 } payload;
56 };
57
58 static_assert(sizeof(Block) == 16, "Block header must be 16 bytes");
59 static_assert(sizeof(Block) == kMinOrderSize,
60 "Minimum allocation size must exactly hold a block header");
61
62 // Describes the layout of a bit-field packed into a 64-bit word.
63 template <size_t begin, size_t end>
64 struct Field {
65 static_assert(begin < sizeof(uint64_t) * 8, "begin is out of bounds");
66 static_assert(end < sizeof(uint64_t) * 8, "end is out of bounds");
67 static_assert(begin <= end, "begin must not be larger than end");
68 static_assert(end - begin + 1 < 64, "must be a part of a word, not a whole word");
69
70 static constexpr uint64_t kMask = (uint64_t(1) << (end - begin + 1)) - 1;
71
72 template <typename T>
MakeField73 static constexpr uint64_t Make(T value) {
74 return static_cast<uint64_t>(value) << begin;
75 }
76
77 template <typename U>
GetField78 static constexpr U Get(uint64_t word) {
79 return static_cast<U>((word >> (begin % 64)) & kMask);
80 }
81
SetField82 static constexpr void Set(uint64_t* word, uint64_t value) {
83 *word = (*word & ~(kMask << begin)) | (value << begin);
84 }
85 };
86
87 // Describes the base fields present for all blocks.
88 struct BlockFields {
89 using Order = Field<0, 3>;
90 using Type = Field<4, 7>;
91 };
92
93 struct HeaderBlockFields : public BlockFields {
94 using Version = Field<8, 31>;
95 using MagicNumber = Field<32, 63>;
96 };
97
98 struct FreeBlockFields : public BlockFields {
99 using NextFreeBlock = Field<8, 35>;
100 };
101
102 // Describes the fields common to all value blocks.
103 struct ValueBlockFields : public BlockFields {
104 using ParentIndex = Field<8, 35>;
105 using NameIndex = Field<36, 63>;
106 };
107
108 struct PropertyBlockPayload {
109 using TotalLength = Field<0, 31>;
110 using ExtentIndex = Field<32, 59>;
111 };
112
113 struct ExtentBlockFields : public BlockFields {
114 using NextExtentIndex = Field<8, 35>;
115 };
116
117 struct NameBlockFields : public BlockFields {
118 using Length = Field<8, 19>;
119 };
120
GetOrder(const Block * block)121 constexpr BlockOrder GetOrder(const Block* block) {
122 return BlockFields::Order::Get<BlockOrder>(block->header);
123 }
124
GetType(const Block * block)125 constexpr BlockType GetType(const Block* block) {
126 return BlockFields::Type::Get<BlockType>(block->header);
127 }
128
PayloadCapacity(BlockOrder order)129 constexpr size_t PayloadCapacity(BlockOrder order) {
130 return OrderToSize(order) - sizeof(Block::header);
131 }
132
BlockSizeForPayload(size_t payload_size)133 constexpr size_t BlockSizeForPayload(size_t payload_size) {
134 return fbl::max(payload_size + sizeof(Block::header), kMinOrderSize);
135 }
136
137 constexpr size_t kMaxPayloadSize = kMaxOrderSize - sizeof(Block::header);
138
139 } // namespace internal
140 } // namespace inspect
141