1 // Copyright 2018 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 <stdbool.h> 8 #include <stdint.h> 9 10 #include <bitmap/rle-bitmap.h> 11 #include <blobfs/format.h> 12 #include <zircon/types.h> 13 14 namespace blobfs { 15 16 // Allows nodes to be reserved and unreserved. The purpose of reservation is to allow allocation of 17 // nodes to occur without yet allocating structures which could be written out to durable storage. 18 // 19 // These nodes may be observed by derived classes of NodeReserver. 20 // Thread-compatible. 21 class NodeReserver { 22 public: 23 // Reserves space for a node in memory. Does not update disk. 24 void Reserve(uint32_t node_index); 25 26 // Unreserves space for a node in memory. Does not update disk. 27 void Unreserve(uint32_t node_index); 28 29 // Returns the total number of reserved nodes. 30 uint32_t ReservedNodeCount() const; 31 32 protected: 33 // Returns true if the node at |node_index| is reserved. 34 bool IsNodeReserved(uint32_t node_index) const; 35 36 // Informs the NodeReserver that |node_index| has been released. 37 // 38 // If |node_index| is lower than the lowest known free node, update our 39 // assumption of the lowest possible free node. 40 void SetFreeNodeLowerBoundIfSmallest(uint32_t node_index); 41 42 // Informs the NodeReserver that |node_index| is the lower bound on free nodes. 43 // 44 // Should only be invoked when it is known that all nodes from [0, node_index) are 45 // free. Does not guarantee |node_index| is free. 46 void SetFreeNodeLowerBound(uint32_t node_index); 47 48 // Returns the earliest possible free node. 49 uint32_t FreeNodeLowerBound() const; 50 51 private: 52 // free_node_lower_bound_ is lower bound on free nodes, meaning we are sure that 53 // there are no free nodes with indices less than free_node_lower_bound_. 54 // 55 // By "free", in this context, we mean both "unreserved and unallocated". 56 // 57 // This doesn't mean that free_node_lower_bound_ is a free node; it just means that one can 58 // start looking for a free node from free_node_lower_bound_. 59 uint32_t free_node_lower_bound_ = 0; 60 bitmap::RleBitmap reserved_nodes_ = {}; 61 }; 62 63 // Wraps a node reservation in RAII to hold the reservation active, and release it when it goes out 64 // of scope. 65 // Thread-compatible. 66 class ReservedNode { 67 public: 68 DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(ReservedNode); 69 70 ReservedNode(NodeReserver* reserver, uint32_t node); 71 ReservedNode(ReservedNode&& o); 72 ReservedNode& operator=(ReservedNode&& o); 73 74 ~ReservedNode(); 75 76 // Access the underlying node index which has been reserved. 77 // 78 // Unsafe to call if the node has not actually been reserved. 79 uint32_t index() const; 80 81 // Releases the underlying node, unreserving it and preventing continued access to |index()|. 82 void Reset(); 83 84 private: 85 // Update internal state such that future calls to |Reserved| return false. 86 void Release(); 87 88 // Identify if the underlying node is reserved, and able to be accessed. 89 bool Reserved() const; 90 91 NodeReserver* reserver_; 92 uint32_t node_; 93 }; 94 95 } // namespace blobfs 96