1// Copyright 2016 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 <bitmap/bitmap.h> 8 9#include <limits.h> 10#include <stddef.h> 11#include <stdint.h> 12#include <string.h> 13 14#include <fbl/algorithm.h> 15#include <fbl/macros.h> 16#include <fbl/type_support.h> 17#include <zircon/assert.h> 18#include <zircon/types.h> 19 20namespace bitmap { 21namespace internal { 22 23DECLARE_HAS_MEMBER_FN(has_grow, Grow); 24 25} // namespace internal 26 27const size_t kBits = sizeof(size_t) * CHAR_BIT; 28 29// Translates a max bit into a final index in the bitmap array. 30constexpr size_t LastIdx(size_t bitmax) { 31 return (bitmax - 1) / kBits; 32} 33 34// Base class for RawGenericBitmap, to reduce what needs to be templated. 35class RawBitmapBase : public Bitmap { 36public: 37 // Returns the size of this bitmap. 38 size_t size() const { return size_; } 39 40 // Shrinks the accessible portion of the bitmap, without re-allocating 41 // the underlying storage. 42 // 43 // This is useful for programs which require underlying bitmap storage 44 // to be aligned to a certain size (initialized via Reset), but want to 45 // restrict access to a smaller portion of the bitmap (via Shrink). 46 zx_status_t Shrink(size_t size); 47 48 // Returns true if all bits in the range [*bitoff*, *bitmax*) match 49 // *is_set*, otherwise returns false and sets *out* (if provided) to the 50 // first (or last, in the case of ReverseScan) bit that doesn't match. An 51 // empty region (i.e. *bitoff* is greater than *bitmax*, or *bitoff* is 52 // outside the range of the bitmap) will return true. 53 bool Scan(size_t bitoff, size_t bitmax, bool is_set, 54 size_t* out = nullptr) const; 55 bool ReverseScan(size_t bitoff, size_t bitmax, bool is_set, 56 size_t* out = nullptr) const; 57 58 // Finds the first (or last, in the case of ReverseFind) run of *run_len* 59 // *is_set* bits, in [*bitoff*, *bitmax*). Returns the start of the run in 60 // *out* and returns ZX_OK if a run is found, otherwise returns 61 // ZX_ERR_NO_RESOURCES. 62 zx_status_t Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len, 63 size_t* out) const override; 64 zx_status_t ReverseFind(bool is_set, size_t bitoff, size_t bitmax, 65 size_t run_len, size_t* out) const; 66 67 // Returns true if all the bits in [*bitoff*, *bitmax*) are set. Afterwards, 68 // *first_unset* will be set to the lesser of bitmax and the index of the 69 // first unset bit after *bitoff*. 70 bool Get(size_t bitoff, size_t bitmax, 71 size_t* first_unset = nullptr) const override; 72 73 // Sets all bits in the range [*bitoff*, *bitmax*). Returns an error if 74 // bitmax < bitoff or size_ < bitmax, and ZX_OK otherwise. 75 zx_status_t Set(size_t bitoff, size_t bitmax) override; 76 77 // Clears all bits in the range [*bitoff*, *bitmax*). Returns an error if 78 // bitmax < bitoff or size_ < bitmax, and ZX_OK otherwise. 79 zx_status_t Clear(size_t bitoff, size_t bitmax) override; 80 81 // Clear all bits in the bitmap. 82 void ClearAll() override; 83 84protected: 85 // The size of this bitmap, in bits. 86 size_t size_ = 0; 87 // Owned by bits_, cached 88 size_t* data_ = nullptr; 89}; 90 91// A simple bitmap backed by generic storage. 92// Storage must implement: 93// - zx_status_t Allocate(size_t size) 94// To allocate |size| bytes of storage. 95// - void* GetData() 96// To access the underlying storage. 97// - zx_status_t Grow(size_t size) 98// (optional) To expand the underlying storage to fit at least |size| 99// bytes. 100template <typename Storage> 101class RawBitmapGeneric final : public RawBitmapBase { 102public: 103 RawBitmapGeneric() = default; 104 virtual ~RawBitmapGeneric() = default; 105 RawBitmapGeneric(RawBitmapGeneric&& rhs) = default; 106 RawBitmapGeneric& operator=(RawBitmapGeneric&& rhs) = default; 107 DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(RawBitmapGeneric); 108 109 // Increases the bitmap size 110 template <typename U = Storage> 111 typename fbl::enable_if<internal::has_grow<U>::value, zx_status_t>::type 112 Grow(size_t size) { 113 if (size < size_) { 114 return ZX_ERR_INVALID_ARGS; 115 } else if (size == size_) { 116 return ZX_OK; 117 } 118 119 size_t old_len = LastIdx(size_) + 1; 120 size_t new_len = LastIdx(size) + 1; 121 size_t new_bitsize = sizeof(size_t) * new_len; 122 ZX_ASSERT(new_bitsize >= new_len); // Overflow 123 zx_status_t status = bits_.Grow(new_bitsize); 124 if (status != ZX_OK) { 125 return status; 126 } 127 128 // Clear all the "newly grown" bytes 129 uintptr_t addr = reinterpret_cast<uintptr_t>(bits_.GetData()) + 130 old_len * sizeof(size_t); 131 memset(reinterpret_cast<void*>(addr), 0, 132 (new_len - old_len) * sizeof(size_t)); 133 134 size_t old_size = size_; 135 data_ = static_cast<size_t*>(bits_.GetData()); 136 size_ = size; 137 138 // Clear the partial bits not included in the new "size_t"s. 139 Clear(old_size, fbl::min(old_len * kBits, size_)); 140 return ZX_OK; 141 } 142 143 template <typename U = Storage> 144 typename fbl::enable_if<!internal::has_grow<U>::value, zx_status_t>::type 145 Grow(size_t size) { 146 return ZX_ERR_NO_RESOURCES; 147 } 148 149 // Resets the bitmap; clearing and resizing it. 150 // Allocates memory, and can fail. 151 zx_status_t Reset(size_t size) { 152 size_ = size; 153 if (size_ == 0) { 154 data_ = nullptr; 155 return ZX_OK; 156 } 157 size_t last_idx = LastIdx(size); 158 zx_status_t status = bits_.Allocate(sizeof(size_t) * (last_idx + 1)); 159 if (status != ZX_OK) { 160 return status; 161 } 162 data_ = static_cast<size_t*>(bits_.GetData()); 163 ClearAll(); 164 return ZX_OK; 165 } 166 167 // This function allows access to underlying data, but is dangerous: It 168 // leaks the pointer to bits_. Reset and the bitmap destructor should not 169 // be called on the bitmap while the pointer returned from data() is alive. 170 const Storage* StorageUnsafe() const { return &bits_; } 171 172private: 173 // The storage backing this bitmap. 174 Storage bits_; 175}; 176 177} // namespace bitmap 178