1270866Simp// Copyright 2016 The Fuchsia Authors. All rights reserved. 2270866Simp// Use of this source code is governed by a BSD-style license that can be 3270866Simp// found in the LICENSE file. 4270866Simp 5270866Simp#include <bitmap/rle-bitmap.h> 6270866Simp 7270866Simp#include <stddef.h> 8270866Simp 9270866Simp#include <zircon/errors.h> 10270866Simp#include <zircon/types.h> 11270866Simp#include <fbl/algorithm.h> 12270866Simp#include <fbl/alloc_checker.h> 13270866Simp 14270866Simpnamespace bitmap { 15270866Simp 16270866Simpnamespace { 17270866Simp 18270866Simp// Allocate a new bitmap element. If *free_list* is null, allocate one using 19270866Simp// new. If *free_list* is not null, take one from *free_list*. 20270866Simpfbl::unique_ptr<RleBitmapElement> AllocateElement(RleBitmap::FreeList* free_list) { 21270866Simp if (!free_list) { 22270866Simp fbl::AllocChecker ac; 23270866Simp fbl::unique_ptr<RleBitmapElement> new_elem(new (&ac) RleBitmapElement()); 24 if (!ac.check()) { 25 return fbl::unique_ptr<RleBitmapElement>(); 26 } 27 return new_elem; 28 } else { 29 return free_list->pop_front(); 30 } 31} 32 33// Release the element *elem*. If *free_list* is null, release the element 34// with delete. If *free_list* is not null, append it to *free_list*. 35void ReleaseElement(RleBitmap::FreeList* free_list, fbl::unique_ptr<RleBitmapElement>&& elem) { 36 if (free_list) { 37 free_list->push_back(fbl::move(elem)); 38 } 39} 40 41} // namespace 42 43zx_status_t RleBitmap::Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len, size_t* out) 44 const { 45 *out = bitmax; 46 47 // Loop through all existing elems to try to find a |run_len| length range of |is_set| bits. 48 // On each loop, |bitoff| is guaranteed to be either within the current elem, or in the range 49 // of unset bits leading up to it. 50 // Therefore, we can check whether |run_len| bits between |bitmax| and |bitoff| exist before 51 // the start of the elem (for unset runs), or within the current elem (for set runs). 52 for (const auto& elem : elems_) { 53 if (bitoff >= elem.end()) { 54 continue; 55 } else if (bitmax - bitoff < run_len) { 56 return ZX_ERR_NO_RESOURCES; 57 } 58 59 size_t elem_min = fbl::max(bitoff, elem.bitoff); // Minimum valid bit within elem. 60 size_t elem_max = fbl::min(bitmax, elem.end()); // Maximum valid bit within elem. 61 62 if (is_set && elem_max > elem_min && elem_max - elem_min >= run_len) { 63 // This element contains at least |run_len| bits 64 // which are between |bitoff| and |bitmax|. 65 *out = elem_min; 66 return ZX_OK; 67 } 68 69 if (!is_set && bitoff < elem.bitoff && elem.bitoff - bitoff >= run_len) { 70 // There are at least |run_len| bits between |bitoff| and the beginning of this element. 71 *out = bitoff; 72 return ZX_OK; 73 } 74 75 if (bitmax < elem.end()) { 76 // We have not found a valid run, and the specified range 77 // does not extend past this element. 78 return ZX_ERR_NO_RESOURCES; 79 } 80 81 // Update bitoff to the next value we want to check within the range. 82 bitoff = elem.end(); 83 } 84 85 86 if (!is_set && bitmax - bitoff >= run_len) { 87 // We have not found an element with bits > bitoff, which means there is an infinite unset 88 // range starting at bitoff. 89 *out = bitoff; 90 return ZX_OK; 91 } 92 93 return ZX_ERR_NO_RESOURCES; 94} 95 96 97bool RleBitmap::Get(size_t bitoff, size_t bitmax, size_t* first_unset) const { 98 for (const auto& elem : elems_) { 99 if (bitoff < elem.bitoff) { 100 break; 101 } 102 if (bitoff < elem.bitoff + elem.bitlen) { 103 bitoff = elem.bitoff + elem.bitlen; 104 break; 105 } 106 } 107 if (bitoff > bitmax) { 108 bitoff = bitmax; 109 } 110 if (first_unset) { 111 *first_unset = bitoff; 112 } 113 114 return bitoff == bitmax; 115} 116 117void RleBitmap::ClearAll() { 118 elems_.clear(); 119 num_elems_ = 0; 120 num_bits_ = 0; 121} 122 123zx_status_t RleBitmap::Set(size_t bitoff, size_t bitmax) { 124 return SetInternal(bitoff, bitmax, nullptr); 125} 126 127zx_status_t RleBitmap::SetNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) { 128 if (free_list == nullptr) { 129 return ZX_ERR_INVALID_ARGS; 130 } 131 132 return SetInternal(bitoff, bitmax, free_list); 133} 134 135zx_status_t RleBitmap::Clear(size_t bitoff, size_t bitmax) { 136 return ClearInternal(bitoff, bitmax, nullptr); 137} 138 139zx_status_t RleBitmap::ClearNoAlloc(size_t bitoff, size_t bitmax, FreeList* free_list) { 140 if (free_list == nullptr) { 141 return ZX_ERR_INVALID_ARGS; 142 } 143 144 return ClearInternal(bitoff, bitmax, free_list); 145} 146 147zx_status_t RleBitmap::SetInternal(size_t bitoff, size_t bitmax, FreeList* free_list) { 148 if (bitmax < bitoff) { 149 return ZX_ERR_INVALID_ARGS; 150 } 151 152 const size_t bitlen = bitmax - bitoff; 153 if (bitlen == 0) { 154 return ZX_OK; 155 } 156 157 fbl::unique_ptr<RleBitmapElement> new_elem = AllocateElement(free_list); 158 if (!new_elem) { 159 return ZX_ERR_NO_MEMORY; 160 } 161 ++num_elems_; 162 new_elem->bitoff = bitoff; 163 new_elem->bitlen = bitlen; 164 165 auto ends_after = elems_.find_if([bitoff](const RleBitmapElement& elem) -> bool { 166 return elem.bitoff + elem.bitlen >= bitoff; 167 }); 168 169 // Insert the new element before the first node that ends at a point >= 170 // when we begin. 171 elems_.insert(ends_after, fbl::move(new_elem)); 172 num_bits_ += bitlen; 173 174 // If ends_after was the end of the list, there is no merging to do. 175 if (ends_after == elems_.end()) { 176 return ZX_OK; 177 } 178 179 auto itr = ends_after; 180 RleBitmapElement& elem = *--ends_after; 181 182 if (elem.bitoff >= itr->bitoff) { 183 // Our range either starts before or in the middle/end of *elem*. 184 // Adjust it so it starts at the same place as *elem*, to allow 185 // the merge logic to not consider this overlap case. 186 elem.bitlen += elem.bitoff - itr->bitoff; 187 num_bits_ += elem.bitoff - itr->bitoff; 188 elem.bitoff = itr->bitoff; 189 } 190 191 // Walk forwards and remove/merge any overlaps 192 size_t max = elem.bitoff + elem.bitlen; 193 while (itr != elems_.end()) { 194 if (itr->bitoff > max) { 195 break; 196 } 197 198 max = fbl::max(max, itr->bitoff + itr->bitlen); 199 num_bits_ += max - elem.bitoff - itr->bitlen - elem.bitlen; 200 elem.bitlen = max - elem.bitoff; 201 auto to_erase = itr; 202 ++itr; 203 ReleaseElement(free_list, elems_.erase(to_erase)); 204 --num_elems_; 205 } 206 207 return ZX_OK; 208} 209 210zx_status_t RleBitmap::ClearInternal(size_t bitoff, size_t bitmax, FreeList* free_list) { 211 if (bitmax < bitoff) { 212 return ZX_ERR_INVALID_ARGS; 213 } 214 215 if (bitmax - bitoff == 0) { 216 return ZX_OK; 217 } 218 219 auto itr = elems_.begin(); 220 while (itr != elems_.end()) { 221 if (itr->bitoff + itr->bitlen < bitoff) { 222 ++itr; 223 continue; 224 } 225 if (bitmax < itr->bitoff) { 226 break; 227 } 228 if (itr->bitoff < bitoff) { 229 if (itr->bitoff + itr->bitlen <= bitmax) { 230 // '*itr' contains 'bitoff'. 231 num_bits_ -= (itr->bitlen - (bitoff - itr->bitoff)); 232 itr->bitlen = bitoff - itr->bitoff; 233 ++itr; 234 continue; 235 } else { 236 // '*itr' contains [bitoff, bitmax), and we need to split it. 237 fbl::unique_ptr<RleBitmapElement> new_elem = AllocateElement(free_list); 238 if (!new_elem) { 239 return ZX_ERR_NO_MEMORY; 240 } 241 ++num_elems_; 242 new_elem->bitoff = bitmax; 243 new_elem->bitlen = itr->bitoff + itr->bitlen - bitmax; 244 245 elems_.insert_after(itr, fbl::move(new_elem)); 246 itr->bitlen = bitoff - itr->bitoff; 247 num_bits_ -= (bitmax - bitoff); 248 break; 249 } 250 } else { 251 if (bitmax < itr->bitoff + itr->bitlen) { 252 // 'elem' contains 'bitmax' 253 num_bits_ -= (bitmax - itr->bitoff); 254 itr->bitlen = itr->bitoff + itr->bitlen - bitmax; 255 itr->bitoff = bitmax; 256 break; 257 } else { 258 // [bitoff, bitmax) fully contains '*itr'. 259 num_bits_ -= itr->bitlen; 260 auto to_erase = itr++; 261 ReleaseElement(free_list, elems_.erase(to_erase)); 262 --num_elems_; 263 } 264 } 265 } 266 267 return ZX_OK; 268} 269 270} // namespace bitmap 271