oxedyne/fe2o3/fe2o3_o3db_sync/src/ns.rs
29.5 KiB, 1 run
created by r1870400018:75877, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! A path namespace over Ozone: byte values under `/`-separated paths, and one index record per |
| 2 | //! directory, `{name → (is_dir, size, mtime_ms)}`, so a directory lists without a `scan`. |
| 3 | //! |
| 4 | //! - **Keys.** A value sits at `ns:{space}:v:{path}`, a directory's index at `ns:{space}:d:{dir}`, |
| 5 | //! the root's at `ns:{space}:d:`. A directory exists while its index record does. |
| 6 | //! - **Spaces.** A space name is non-empty and holds no `:`, so no two spaces share a key. |
| 7 | //! - **Order.** An index record exists only while its parent lists it. `put` writes the value, |
| 8 | //! then the index records top-down (a parent it made first), so a crash leaves at worst a |
| 9 | //! parent listing a directory whose record is not there yet; that entry reads as absent and the |
| 10 | //! next `put` through it writes the record. `delete` drops a value's entry before the value, and |
| 11 | //! a directory's record before its entry. `delete_tree` deletes the values, then the records |
| 12 | //! deepest first, then the entry. `rename` copies, links the copy top-down, makes it all |
| 13 | //! durable with one `sync_now` barrier, then deletes the original as `delete_tree` does. |
| 14 | //! - **The crash model.** A process crash (a panic, an OOM kill, `SIGKILL`) is always safe: each |
| 15 | //! step waits for its ack, and an acked record is in the page cache, which outlives the |
| 16 | //! process. A power loss or kernel crash can lose the writes of the last sync interval, and, |
| 17 | //! since the zones sync on their own timers, keep a later write while losing an earlier one. |
| 18 | //! `rename`'s barrier means it still never leaves neither tree, and `put` climbs until a parent |
| 19 | //! already lists the child (not merely until a record exists), so a directory record whose |
| 20 | //! parent's entry was lost is listed again by the next `put` through it: the tree heals. |
| 21 | //! - **Reads trust the index only so far.** `stat` and `list` ignore an entry whose value (or, for |
| 22 | //! a directory, whose index record) is absent, and `put` replaces such a dead entry. |
| 23 | //! - **One mutation lane.** Every mutation holds the handle's FIFO lane ([`O3db::ns_lane`]) across |
| 24 | //! its reads, checks and writes, including the parent index's read-modify-write, so a second |
| 25 | //! `Ns` over the same handle cannot interleave with it. Reads take no lane. `put_if` and |
| 26 | //! `delete_if` run their `pred` under it, so a mutation called from inside `pred` is refused. |
| 27 | //! - **Orphans.** A crash leaves values and directory records that no live chain reaches; |
| 28 | //! [`orphans`] finds them by walking the store, for a background sweep only. Its list is valid |
| 29 | //! only while the lane is held: a torn `put` leaves an orphan at the very key a later `put` |
| 30 | //! makes live, so whatever deletes orphans must re-check each under the lane as it deletes. |
| 31 | //! |
| 32 | //! Meant for a single caller thread (the lane makes other threads safe, not fast). Nothing on a |
| 33 | //! request path may scan; only [`orphans`] and [`sweep_orphans`] do, from `sweep`. |
| 34 | //! - **Retirement (the Ozone sweep).** `delete_range` deletes a directory's entries whose names |
| 35 | //! fall in a range; `sweep_expired` deletes those older than a TTL on the caller's clock; both |
| 36 | //! read index records only. [`sweep_orphans`] deletes what [`orphans`] finds, re-checking each |
| 37 | //! under the lane as it deletes. |
| 38 | //! |
| 39 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 40 | //! Anthropic Claude |
| 41 | |
| 42 | use crate::{ |
| 43 | O3db, |
| 44 | comm::response::Wait, |
| 45 | test::hooks::{ |
| 46 | self, |
| 47 | NsStep, |
| 48 | NsTear, |
| 49 | }, |
| 50 | }; |
| 51 | |
| 52 | use oxedyne_fe2o3_core::prelude::*; |
| 53 | use oxedyne_fe2o3_iop_crypto::enc::Encrypter; |
| 54 | use oxedyne_fe2o3_iop_hash::{ |
| 55 | api::Hasher, |
| 56 | csum::Checksummer, |
| 57 | }; |
| 58 | use oxedyne_fe2o3_jdat::{ |
| 59 | prelude::*, |
| 60 | id::NumIdDat, |
| 61 | }; |
| 62 | |
| 63 | use std::{ |
| 64 | collections::BTreeMap, |
| 65 | sync::{ |
| 66 | Arc, |
| 67 | Condvar, |
| 68 | Mutex, |
| 69 | }, |
| 70 | thread::{ |
| 71 | self, |
| 72 | ThreadId, |
| 73 | }, |
| 74 | time::{ |
| 75 | SystemTime, |
| 76 | UNIX_EPOCH, |
| 77 | }, |
| 78 | }; |
| 79 | |
| 80 | |
| 81 | /// A FIFO ticket lock: holders are served in the order they asked. It is not re-entrant, so a |
| 82 | /// thread that asks again while holding it is refused rather than left waiting on itself. |
| 83 | #[derive(Debug, Default)] |
| 84 | pub struct Lane { |
| 85 | turn: Mutex<Turn>, |
| 86 | moved: Condvar, |
| 87 | } |
| 88 | |
| 89 | #[derive(Debug, Default)] |
| 90 | struct Turn { |
| 91 | next: u64, // the next ticket to hand out |
| 92 | serving: u64, // the ticket being served |
| 93 | holder: Option<ThreadId>, // the thread being served |
| 94 | } |
| 95 | |
| 96 | /// The lane, held until dropped. |
| 97 | #[derive(Debug)] |
| 98 | pub(crate) struct LaneHold<'a> { |
| 99 | lane: &'a Lane, |
| 100 | } |
| 101 | |
| 102 | impl Lane { |
| 103 | pub(crate) fn hold(&self) -> Outcome<LaneHold<'_>> { |
| 104 | let me = thread::current().id(); |
| 105 | let mut turn = lock_mutex!(self.turn, "Taking a ticket for the ns mutation lane."); |
| 106 | if turn.holder == Some(me) { |
| 107 | return Err(err!( |
| 108 | "This thread already holds the ns mutation lane, so a mutation called from inside \ |
| 109 | another (a put_if or delete_if predicate, say) is refused rather than left waiting \ |
| 110 | on itself."; |
| 111 | Lock, Conflict)); |
| 112 | } |
| 113 | let mine = turn.next; |
| 114 | turn.next = turn.next.wrapping_add(1); |
| 115 | while turn.serving != mine { |
| 116 | turn = match self.moved.wait(turn) { |
| 117 | Ok(t) => t, |
| 118 | // As in `Drop`: returning here would leave ticket `mine` taken and never served, |
| 119 | // so every later holder would wait for ever. |
| 120 | Err(p) => p.into_inner(), |
| 121 | }; |
| 122 | } |
| 123 | turn.holder = Some(me); |
| 124 | Ok(LaneHold { lane: self }) |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | impl Drop for LaneHold<'_> { |
| 129 | fn drop(&mut self) { |
| 130 | // A poisoned lock still passes the turn on, or every later holder would wait for ever. |
| 131 | let mut turn = match self.lane.turn.lock() { |
| 132 | Ok(t) => t, |
| 133 | Err(p) => p.into_inner(), |
| 134 | }; |
| 135 | turn.holder = None; |
| 136 | turn.serving = turn.serving.wrapping_add(1); |
| 137 | self.lane.moved.notify_all(); |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | /// One index entry. |
| 142 | #[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] |
| 143 | pub struct Entry { |
| 144 | pub is_dir: bool, |
| 145 | pub size: u64, // bytes; 0 for a directory |
| 146 | pub mtime_ms: u64, // ms since the Unix epoch |
| 147 | } |
| 148 | |
| 149 | /// What `get_capped` found. |
| 150 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 151 | pub enum Capped { |
| 152 | Absent, |
| 153 | Whole(Vec<u8>), |
| 154 | Over(u64), // the size, over the cap; the value is not read |
| 155 | } |
| 156 | |
| 157 | /// What [`orphans`] found: values and directory index records that no chain of live entries |
| 158 | /// from the root reaches. |
| 159 | #[derive(Clone, Debug, Default, PartialEq, Eq)] |
| 160 | pub struct Orphans { |
| 161 | pub values: Vec<String>, // paths |
| 162 | pub dirs: Vec<String>, // paths |
| 163 | } |
| 164 | |
| 165 | pub use crate::sweep::ns_orphans as orphans; |
| 166 | pub use crate::sweep::ns_sweep_orphans as sweep_orphans; |
| 167 | |
| 168 | type Index = BTreeMap<String, Entry>; |
| 169 | |
| 170 | pub fn now_ms() -> u64 { |
| 171 | match SystemTime::now().duration_since(UNIX_EPOCH) { |
| 172 | Ok(d) => d.as_millis() as u64, |
| 173 | Err(_) => 0, |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | /// Splits a non-root path into its parent directory and its name. |
| 178 | fn split(path: &str) -> (&str, &str) { |
| 179 | match path.rfind('/') { |
| 180 | Some(i) => (&path[..i], &path[i + 1..]), |
| 181 | None => ("", path), |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | /// A path is `/`-separated names, none empty, `.` or `..`, with no NUL; `""` is the root. |
| 186 | fn check_path(path: &str, root_ok: bool) -> Outcome<()> { |
| 187 | if path.is_empty() { |
| 188 | if root_ok { |
| 189 | return Ok(()); |
| 190 | } |
| 191 | return Err(err!("An ns path must not be the root here."; Invalid, Input, Path)); |
| 192 | } |
| 193 | for part in path.split('/') { |
| 194 | if part.is_empty() || part == "." || part == ".." || part.contains('\0') { |
| 195 | return Err(err!( |
| 196 | "The ns path '{}' has an empty, '.', '..' or NUL-bearing part.", path; |
| 197 | Invalid, Input, Path)); |
| 198 | } |
| 199 | } |
| 200 | Ok(()) |
| 201 | } |
| 202 | |
| 203 | /// A path namespace in one `space` of an [`O3db`]. |
| 204 | pub struct Ns< |
| 205 | const UIDL: usize, |
| 206 | UID: NumIdDat<UIDL> + 'static, |
| 207 | ENC: Encrypter + 'static, |
| 208 | KH: Hasher + 'static, |
| 209 | PR: Hasher + 'static, |
| 210 | CS: Checksummer + 'static, |
| 211 | > { |
| 212 | db: Arc<O3db<UIDL, UID, ENC, KH, PR, CS>>, |
| 213 | user: UID, // stamped on every write |
| 214 | space: String, |
| 215 | } |
| 216 | |
| 217 | impl< |
| 218 | const UIDL: usize, |
| 219 | UID: NumIdDat<UIDL> + 'static, |
| 220 | ENC: Encrypter + 'static, |
| 221 | KH: Hasher + 'static, |
| 222 | PR: Hasher + 'static, |
| 223 | CS: Checksummer + 'static, |
| 224 | > |
| 225 | Ns<UIDL, UID, ENC, KH, PR, CS> |
| 226 | { |
| 227 | /// A `space` must be non-empty and hold no `:`, or space `x` with path `v:p` and space `x:v` |
| 228 | /// with path `p` would share the key `ns:x:v:v:p`. |
| 229 | pub fn new(db: Arc<O3db<UIDL, UID, ENC, KH, PR, CS>>, user: UID, space: &str) |
| 230 | -> Outcome<Self> |
| 231 | { |
| 232 | if space.is_empty() || space.contains(':') { |
| 233 | return Err(err!( |
| 234 | "The ns space name '{}' is empty or holds a ':', so its keys could be another \ |
| 235 | space's.", space; |
| 236 | Invalid, Input)); |
| 237 | } |
| 238 | Ok(Self { db, user, space: space.to_string() }) |
| 239 | } |
| 240 | |
| 241 | pub fn db(&self) -> &Arc<O3db<UIDL, UID, ENC, KH, PR, CS>> { &self.db } |
| 242 | pub fn space(&self) -> &str { &self.space } |
| 243 | |
| 244 | pub fn value_key(&self, path: &str) -> Dat { |
| 245 | Dat::Str(fmt!("ns:{}:v:{}", self.space, path)) |
| 246 | } |
| 247 | |
| 248 | pub fn index_key(&self, dir: &str) -> Dat { |
| 249 | Dat::Str(fmt!("ns:{}:d:{}", self.space, dir)) |
| 250 | } |
| 251 | |
| 252 | // ── Reads ──────────────────────────────────────────────────────────────────────────────── |
| 253 | |
| 254 | /// The value at `path`, as stored (an orphan value with no index entry included). |
| 255 | pub fn get(&self, path: &str) -> Outcome<Option<Vec<u8>>> { |
| 256 | res!(check_path(path, false)); |
| 257 | match res!(self.db.api().get_wait(&self.value_key(path), None)) { |
| 258 | None => Ok(None), |
| 259 | Some((dat, _)) => Ok(Some(res!(Self::bytes_of(dat, path)))), |
| 260 | } |
| 261 | } |
| 262 | |
| 263 | /// The value at `path` if its indexed size is at most `cap`; a larger one is not read. |
| 264 | pub fn get_capped(&self, path: &str, cap: u64) -> Outcome<Capped> { |
| 265 | match res!(self.stat(path)) { |
| 266 | None => return Ok(Capped::Absent), |
| 267 | Some(e) if e.is_dir => return Err(err!( |
| 268 | "The ns path '{}' is a directory, not a value.", path; Invalid, Input, Path)), |
| 269 | Some(e) if e.size > cap => return Ok(Capped::Over(e.size)), |
| 270 | Some(_) => (), |
| 271 | } |
| 272 | match res!(self.get(path)) { |
| 273 | None => Ok(Capped::Absent), |
| 274 | Some(b) if b.len() as u64 > cap => Ok(Capped::Over(b.len() as u64)), |
| 275 | Some(b) => Ok(Capped::Whole(b)), |
| 276 | } |
| 277 | } |
| 278 | |
| 279 | /// The index entry for `path`, if it is there and what it names is too. The root is a directory. |
| 280 | pub fn stat(&self, path: &str) -> Outcome<Option<Entry>> { |
| 281 | res!(check_path(path, true)); |
| 282 | if path.is_empty() { |
| 283 | return Ok(Some(Entry { is_dir: true, size: 0, mtime_ms: 0 })); |
| 284 | } |
| 285 | let (dir, name) = split(path); |
| 286 | let entry = match res!(self.read_index(dir)) { |
| 287 | None => return Ok(None), |
| 288 | Some(idx) => match idx.get(name) { |
| 289 | None => return Ok(None), |
| 290 | Some(e) => *e, |
| 291 | }, |
| 292 | }; |
| 293 | let key = self.backing_key(path, &entry); |
| 294 | if res!(self.db.api().contains_wait(&key, None)) { |
| 295 | Ok(Some(entry)) |
| 296 | } else { |
| 297 | Ok(None) |
| 298 | } |
| 299 | } |
| 300 | |
| 301 | /// The live entries of directory `dir`, by name; `None` when it does not exist. |
| 302 | pub fn list(&self, dir: &str) -> Outcome<Option<Vec<(String, Entry)>>> { |
| 303 | res!(check_path(dir, true)); |
| 304 | let idx = match res!(self.read_index(dir)) { |
| 305 | Some(idx) => idx, |
| 306 | None if dir.is_empty() => return Ok(Some(Vec::new())), |
| 307 | None => return Ok(None), |
| 308 | }; |
| 309 | if idx.is_empty() { |
| 310 | return Ok(Some(Vec::new())); |
| 311 | } |
| 312 | let mut keys = Vec::with_capacity(idx.len()); |
| 313 | for (name, e) in &idx { |
| 314 | keys.push(self.backing_key(&Self::join(dir, name), e)); |
| 315 | } |
| 316 | let held = res!(self.db.api().contains_many_wait(&keys, None)); |
| 317 | let mut out = Vec::with_capacity(idx.len()); |
| 318 | for (i, (name, e)) in idx.into_iter().enumerate() { |
| 319 | if held.get(i) == Some(&true) { |
| 320 | out.push((name, e)); |
| 321 | } |
| 322 | } |
| 323 | Ok(Some(out)) |
| 324 | } |
| 325 | |
| 326 | // ── Mutations, each under the lane ─────────────────────────────────────────────────────── |
| 327 | |
| 328 | pub fn put(&self, path: &str, bytes: &[u8]) -> Outcome<()> { |
| 329 | self.put_at(path, bytes, now_ms()) |
| 330 | } |
| 331 | |
| 332 | /// `put` with the entry's mtime given. Parents are made, stamped `mtime_ms`. |
| 333 | pub fn put_at(&self, path: &str, bytes: &[u8], mtime_ms: u64) -> Outcome<()> { |
| 334 | res!(check_path(path, false)); |
| 335 | let _hold = res!(self.db.ns_lane().hold()); |
| 336 | self.put_held(path, bytes, mtime_ms) |
| 337 | } |
| 338 | |
| 339 | /// Puts `bytes` at `path` only if `pred` passes on its current entry (`None` when absent), |
| 340 | /// all under the lane. Whether it was put. |
| 341 | pub fn put_if<F>(&self, path: &str, bytes: &[u8], pred: F) -> Outcome<bool> |
| 342 | where F: FnOnce(Option<&Entry>) -> bool |
| 343 | { |
| 344 | res!(check_path(path, false)); |
| 345 | let _hold = res!(self.db.ns_lane().hold()); |
| 346 | let now = res!(self.stat(path)); |
| 347 | if !pred(now.as_ref()) { |
| 348 | return Ok(false); |
| 349 | } |
| 350 | res!(self.put_held(path, bytes, now_ms())); |
| 351 | Ok(true) |
| 352 | } |
| 353 | |
| 354 | /// Makes the directory `path` and every directory above it that is not there, as a filesystem |
| 355 | /// makes a file's folders on its way down. What stands is kept: a directory already there, |
| 356 | /// and all in it, is left as it is. A value at `path` or above it is a `Conflict`, and then |
| 357 | /// nothing is made. |
| 358 | pub fn make_dirs(&self, path: &str) -> Outcome<()> { |
| 359 | res!(check_path(path, false)); |
| 360 | let _hold = res!(self.db.ns_lane().hold()); |
| 361 | match res!(self.stat(path)) { |
| 362 | Some(e) if e.is_dir => return Ok(()), |
| 363 | Some(_) => return Err(err!( |
| 364 | "The ns path '{}' is a value, so it cannot be made a directory.", path; |
| 365 | Conflict, Path)), |
| 366 | None => (), |
| 367 | } |
| 368 | res!(self.link_held(path, Entry { is_dir: true, size: 0, mtime_ms: now_ms() })); |
| 369 | // Its own record last, top-down: a crash before it leaves an entry that reads as absent. |
| 370 | if res!(self.read_index(path)).is_none() { |
| 371 | res!(self.write_index(path, &Index::new())); |
| 372 | } |
| 373 | Ok(()) |
| 374 | } |
| 375 | |
| 376 | /// Deletes the value at `path`, or the empty directory there. Whether an entry was listed. |
| 377 | pub fn delete(&self, path: &str) -> Outcome<bool> { |
| 378 | res!(check_path(path, false)); |
| 379 | let _hold = res!(self.db.ns_lane().hold()); |
| 380 | self.delete_held(path) |
| 381 | } |
| 382 | |
| 383 | /// `delete` only if `pred` passes on the current entry (`None` when absent), all under the |
| 384 | /// lane. Whether `pred` passed. |
| 385 | pub fn delete_if<F>(&self, path: &str, pred: F) -> Outcome<bool> |
| 386 | where F: FnOnce(Option<&Entry>) -> bool |
| 387 | { |
| 388 | res!(check_path(path, false)); |
| 389 | let _hold = res!(self.db.ns_lane().hold()); |
| 390 | let now = res!(self.stat(path)); |
| 391 | if !pred(now.as_ref()) { |
| 392 | return Ok(false); |
| 393 | } |
| 394 | res!(self.delete_held(path)); |
| 395 | Ok(true) |
| 396 | } |
| 397 | |
| 398 | /// Deletes `path` and everything under it, dead entries' remains included: values first, then |
| 399 | /// index records deepest first, then the parent's entry, so a crash leaves only dead entries. |
| 400 | /// The number of values gone. |
| 401 | pub fn delete_tree(&self, path: &str) -> Outcome<usize> { |
| 402 | res!(check_path(path, false)); |
| 403 | let _hold = res!(self.db.ns_lane().hold()); |
| 404 | self.delete_tree_held(path) |
| 405 | } |
| 406 | |
| 407 | /// Deletes every entry of directory `dir` whose name `n` has `from <= n < to`, each as |
| 408 | /// `delete_tree` does (a subdirectory with all under it), in one hold of the lane. It reads |
| 409 | /// the directory's index, never the store, so it may run on a request path. The number of |
| 410 | /// values gone; nothing when `dir` is absent or the range is empty. |
| 411 | pub fn delete_range(&self, dir: &str, from: &str, to: &str) -> Outcome<usize> { |
| 412 | res!(check_path(dir, true)); |
| 413 | let _hold = res!(self.db.ns_lane().hold()); |
| 414 | let idx = match res!(self.read_index(dir)) { |
| 415 | Some(idx) => idx, |
| 416 | None => return Ok(0), |
| 417 | }; |
| 418 | let mut gone = 0; |
| 419 | for name in idx.keys().filter(|n| n.as_str() >= from && n.as_str() < to) { |
| 420 | gone += res!(self.delete_tree_held(&Self::join(dir, name))); |
| 421 | } |
| 422 | Ok(gone) |
| 423 | } |
| 424 | |
| 425 | /// The TTL sweep of directory `dir`: deletes, as `delete_tree` does, every entry whose age at |
| 426 | /// `now_ms` is at least `ttl_ms`, in one hold of the lane. A value's age runs from its mtime; |
| 427 | /// a subdirectory's from the newest mtime of it and everything under it, so a run journal |
| 428 | /// written to yesterday stays however old its first round. A mtime after `now_ms` (the clock |
| 429 | /// stepped back) is age 0, so kept. The clock is the caller's, so a test can fake it. It |
| 430 | /// walks `dir`'s index records only, never the store. The number of values gone. |
| 431 | pub fn sweep_expired(&self, dir: &str, ttl_ms: u64, now_ms: u64) -> Outcome<usize> { |
| 432 | res!(check_path(dir, true)); |
| 433 | let _hold = res!(self.db.ns_lane().hold()); |
| 434 | let idx = match res!(self.read_index(dir)) { |
| 435 | Some(idx) => idx, |
| 436 | None => return Ok(0), |
| 437 | }; |
| 438 | let mut gone = 0; |
| 439 | for (name, e) in &idx { |
| 440 | let path = Self::join(dir, name); |
| 441 | let newest = if e.is_dir { |
| 442 | res!(self.newest_mtime(&path, e.mtime_ms)) |
| 443 | } else { |
| 444 | e.mtime_ms |
| 445 | }; |
| 446 | if now_ms.saturating_sub(newest) >= ttl_ms { |
| 447 | gone += res!(self.delete_tree_held(&path)); |
| 448 | } |
| 449 | } |
| 450 | Ok(gone) |
| 451 | } |
| 452 | |
| 453 | // The newest mtime of directory `path`'s entries, all the way down, and `floor`. |
| 454 | fn newest_mtime(&self, path: &str, floor: u64) -> Outcome<u64> { |
| 455 | let mut newest = floor; |
| 456 | let mut todo = vec![path.to_string()]; |
| 457 | while let Some(dir) = todo.pop() { |
| 458 | let idx = match res!(self.read_index(&dir)) { |
| 459 | Some(idx) => idx, |
| 460 | None => continue, |
| 461 | }; |
| 462 | for (name, e) in idx { |
| 463 | newest = newest.max(e.mtime_ms); |
| 464 | if e.is_dir { |
| 465 | todo.push(Self::join(&dir, &name)); |
| 466 | } |
| 467 | } |
| 468 | } |
| 469 | Ok(newest) |
| 470 | } |
| 471 | |
| 472 | /// Moves the value or tree at `from` to `to`, which must be absent and not inside `from`. |
| 473 | /// The values are copied, `to` is linked and its index records written top-down, then `from` |
| 474 | /// goes as `delete_tree` does. A crash leaves `from` whole, or `to` whole, or both. |
| 475 | pub fn rename(&self, from: &str, to: &str) -> Outcome<()> { |
| 476 | res!(check_path(from, false)); |
| 477 | res!(check_path(to, false)); |
| 478 | if to == from || to.starts_with(&fmt!("{}/", from)) { |
| 479 | return Err(err!( |
| 480 | "The ns path '{}' cannot be renamed to '{}', which is itself or inside it.", from, to; |
| 481 | Invalid, Input, Path)); |
| 482 | } |
| 483 | let _hold = res!(self.db.ns_lane().hold()); |
| 484 | let top = match res!(self.stat(from)) { |
| 485 | Some(e) => e, |
| 486 | None => return Err(err!("The ns path '{}' is absent, so not renamed.", from; |
| 487 | Missing, Path)), |
| 488 | }; |
| 489 | if res!(self.stat(to)).is_some() { |
| 490 | return Err(err!("The ns path '{}' already exists, so '{}' is not renamed onto it.", |
| 491 | to, from; Exists, Path)); |
| 492 | } |
| 493 | if !top.is_dir { |
| 494 | res!(self.copy_value(from, to)); |
| 495 | res!(self.link_held(to, top)); |
| 496 | res!(self.barrier()); |
| 497 | res!(self.delete_held(from)); |
| 498 | return Ok(()); |
| 499 | } |
| 500 | // Live entries only. The values go in unreachable; each index record is planned parent first. |
| 501 | let mut plan: Vec<(String, Index)> = Vec::new(); |
| 502 | let mut todo = vec![String::new()]; |
| 503 | while let Some(rel) = todo.pop() { |
| 504 | let live = match res!(self.list(&Self::join(from, &rel))) { |
| 505 | Some(live) => live, |
| 506 | None => Vec::new(), |
| 507 | }; |
| 508 | let mut idx = Index::new(); |
| 509 | for (name, e) in live { |
| 510 | let sub = Self::join(&rel, &name); |
| 511 | if e.is_dir { |
| 512 | todo.push(sub); |
| 513 | } else { |
| 514 | res!(self.copy_value(&Self::join(from, &sub), &Self::join(to, &sub))); |
| 515 | } |
| 516 | idx.insert(name, e); |
| 517 | } |
| 518 | plan.push((rel, idx)); |
| 519 | } |
| 520 | res!(self.link_held(to, top)); |
| 521 | for (rel, idx) in plan { |
| 522 | res!(self.write_index(&Self::join(to, &rel), &idx)); |
| 523 | } |
| 524 | res!(self.barrier()); |
| 525 | res!(self.delete_tree_held(from)); |
| 526 | Ok(()) |
| 527 | } |
| 528 | |
| 529 | // Every write so far durable, across every zone: an ack alone means the page cache, and two |
| 530 | // zones sync on their own timers, so a power loss could otherwise keep `from`'s later |
| 531 | // deletes and lose `to`'s earlier writes, leaving neither. |
| 532 | fn barrier(&self) -> Outcome<()> { |
| 533 | res!(self.db.api().sync_now(Wait::default())); |
| 534 | hooks::ns_trace(NsStep::Barrier); |
| 535 | Ok(()) |
| 536 | } |
| 537 | |
| 538 | // ── Lane-held bodies ───────────────────────────────────────────────────────────────────── |
| 539 | |
| 540 | fn put_held(&self, path: &str, bytes: &[u8], mtime_ms: u64) -> Outcome<()> { |
| 541 | let mut writes = res!(self.plan_link(path, |
| 542 | Entry { is_dir: false, size: bytes.len() as u64, mtime_ms })); |
| 543 | let resp = res!(self.db.api().store( |
| 544 | self.value_key(path), Dat::wrap_dat(bytes.to_vec()), self.user)); |
| 545 | res!(resp.recv_store_ack()); |
| 546 | // Top-down: a process crash leaves a parent listing a directory whose index is not yet |
| 547 | // there, which reads as absent, and the next put through it lists it again. |
| 548 | writes.reverse(); |
| 549 | match hooks::ns_tear() { |
| 550 | None => (), |
| 551 | Some(NsTear::Top(n)) => writes.truncate(n), |
| 552 | Some(NsTear::Deep(n)) => { |
| 553 | let lost = writes.len().saturating_sub(n); |
| 554 | writes.drain(..lost); |
| 555 | }, |
| 556 | } |
| 557 | for (dir, idx) in writes { |
| 558 | res!(self.write_index(&dir, &idx)); |
| 559 | } |
| 560 | Ok(()) |
| 561 | } |
| 562 | |
| 563 | // Lists `path` as `entry` in its parent, making parents, top-down. |
| 564 | fn link_held(&self, path: &str, entry: Entry) -> Outcome<()> { |
| 565 | let writes = res!(self.plan_link(path, entry)); |
| 566 | for (dir, idx) in writes.into_iter().rev() { |
| 567 | res!(self.write_index(&dir, &idx)); |
| 568 | } |
| 569 | Ok(()) |
| 570 | } |
| 571 | |
| 572 | // The index writes, leaf first, that list `path` as `entry` and make its parents. Planned |
| 573 | // before anything is written, so a conflict leaves nothing behind. A dead entry (whose value |
| 574 | // or index is absent) is no conflict: it is replaced. It climbs until a parent already lists |
| 575 | // the child as a directory, not merely until a record exists, so a record that reached the |
| 576 | // disk while its parent's new entry did not (a power loss can keep them in either order) is |
| 577 | // listed again here. |
| 578 | fn plan_link(&self, path: &str, entry: Entry) -> Outcome<Vec<(String, Index)>> { |
| 579 | let mut writes: Vec<(String, Index)> = Vec::new(); |
| 580 | let mut child = path.to_string(); |
| 581 | let mut entry = entry; |
| 582 | let mtime_ms = entry.mtime_ms; |
| 583 | loop { |
| 584 | let (dir, name) = split(&child); |
| 585 | let (dir, name) = (dir.to_string(), name.to_string()); |
| 586 | let mut idx = match res!(self.read_index(&dir)) { |
| 587 | Some(idx) => idx, |
| 588 | None => Index::new(), |
| 589 | }; |
| 590 | if let Some(old) = idx.get(&name) { |
| 591 | let live = res!(self.db.api().contains_wait(&self.backing_key(&child, old), None)); |
| 592 | if live && old.is_dir != entry.is_dir { |
| 593 | return Err(err!( |
| 594 | "The ns path '{}' is a {}, so '{}' cannot be put.", child, |
| 595 | if old.is_dir { "directory" } else { "value" }, path; |
| 596 | Conflict, Path)); |
| 597 | } |
| 598 | // A directory its parent already lists: nothing above changes. |
| 599 | if old.is_dir && entry.is_dir { |
| 600 | break; |
| 601 | } |
| 602 | } |
| 603 | idx.insert(name, entry); |
| 604 | writes.push((dir.clone(), idx)); |
| 605 | if dir.is_empty() { |
| 606 | break; |
| 607 | } |
| 608 | child = dir; |
| 609 | entry = Entry { is_dir: true, size: 0, mtime_ms }; |
| 610 | } |
| 611 | Ok(writes) |
| 612 | } |
| 613 | |
| 614 | fn delete_held(&self, path: &str) -> Outcome<bool> { |
| 615 | let (dir, name) = split(path); |
| 616 | let mut idx = match res!(self.read_index(dir)) { |
| 617 | Some(idx) => idx, |
| 618 | None => Index::new(), |
| 619 | }; |
| 620 | match idx.remove(name) { |
| 621 | Some(e) if e.is_dir => { |
| 622 | // Only live entries count: a dead one (left by a crash) does not keep it. |
| 623 | if let Some(inner) = res!(self.list(path)) { |
| 624 | if !inner.is_empty() { |
| 625 | return Err(err!( |
| 626 | "The ns directory '{}' holds {} entries, so it is not deleted.", |
| 627 | path, inner.len(); |
| 628 | Conflict, Path)); |
| 629 | } |
| 630 | } |
| 631 | res!(self.remove_key(&self.index_key(path))); |
| 632 | res!(self.write_index(dir, &idx)); |
| 633 | Ok(true) |
| 634 | }, |
| 635 | Some(_) => { |
| 636 | res!(self.write_index(dir, &idx)); |
| 637 | res!(self.remove_key(&self.value_key(path))); |
| 638 | Ok(true) |
| 639 | }, |
| 640 | None => { |
| 641 | res!(self.remove_key(&self.value_key(path))); |
| 642 | Ok(false) |
| 643 | }, |
| 644 | } |
| 645 | } |
| 646 | |
| 647 | fn delete_tree_held(&self, path: &str) -> Outcome<usize> { |
| 648 | let (values, dirs) = res!(self.tree_keys(path)); |
| 649 | for key in values.iter().chain(dirs.iter().rev()) { |
| 650 | res!(self.remove_key(key)); |
| 651 | } |
| 652 | let (dir, name) = split(path); |
| 653 | if let Some(mut idx) = res!(self.read_index(dir)) { |
| 654 | if idx.remove(name).is_some() { |
| 655 | res!(self.write_index(dir, &idx)); |
| 656 | } |
| 657 | } |
| 658 | Ok(values.len()) |
| 659 | } |
| 660 | |
| 661 | // Every value key and directory index key at and under `path`, dead entries included; the |
| 662 | // directories parent first. |
| 663 | fn tree_keys(&self, path: &str) -> Outcome<(Vec<Dat>, Vec<Dat>)> { |
| 664 | let mut values = vec![self.value_key(path)]; |
| 665 | let mut dirs = Vec::new(); |
| 666 | let mut todo = vec![path.to_string()]; |
| 667 | while let Some(dir) = todo.pop() { |
| 668 | let idx = match res!(self.read_index(&dir)) { |
| 669 | Some(idx) => idx, |
| 670 | None => continue, |
| 671 | }; |
| 672 | for (name, e) in idx { |
| 673 | let sub = Self::join(&dir, &name); |
| 674 | if e.is_dir { |
| 675 | todo.push(sub); |
| 676 | } else { |
| 677 | values.push(self.value_key(&sub)); |
| 678 | } |
| 679 | } |
| 680 | dirs.push(self.index_key(&dir)); |
| 681 | } |
| 682 | // Only what is there: the count is of values gone. |
| 683 | let held = res!(self.db.api().contains_many_wait(&values, None)); |
| 684 | let values = values.into_iter().enumerate() |
| 685 | .filter(|(i, _)| held.get(*i) == Some(&true)) |
| 686 | .map(|(_, k)| k) |
| 687 | .collect(); |
| 688 | Ok((values, dirs)) |
| 689 | } |
| 690 | |
| 691 | fn copy_value(&self, from: &str, to: &str) -> Outcome<()> { |
| 692 | let bytes = match res!(self.get(from)) { |
| 693 | Some(b) => b, |
| 694 | None => return Err(err!("The ns value at '{}' went while being copied.", from; |
| 695 | Missing, Path)), |
| 696 | }; |
| 697 | let resp = res!(self.db.api().store(self.value_key(to), Dat::wrap_dat(bytes), self.user)); |
| 698 | res!(resp.recv_store_ack()); |
| 699 | Ok(()) |
| 700 | } |
| 701 | |
| 702 | fn remove_key(&self, key: &Dat) -> Outcome<()> { |
| 703 | if res!(self.db.api().contains_wait(key, None)) { |
| 704 | hooks::ns_trace(NsStep::Delete); |
| 705 | let resp = self.db.api().responder(); |
| 706 | res!(self.db.api().delete_using_responder(key, self.user, None, resp.clone())); |
| 707 | res!(resp.recv_delete_ack()); |
| 708 | } |
| 709 | Ok(()) |
| 710 | } |
| 711 | |
| 712 | // ── Orphans ────────────────────────────────────────────────────────────────────────────── |
| 713 | |
| 714 | /// Of the keys a walk of the store found, those of this space no live chain reaches, judged |
| 715 | /// under the lane so that no put is part way through. |
| 716 | pub(crate) fn confirm_orphans(&self, keys: Vec<Dat>) -> Outcome<Orphans> { |
| 717 | let _hold = res!(self.db.ns_lane().hold()); |
| 718 | self.confirm_orphans_held(keys) |
| 719 | } |
| 720 | |
| 721 | /// Confirms the orphans among `keys` as `confirm_orphans` does and deletes them, values |
| 722 | /// first, all in one hold of the lane, so no put can make one live between the check and its |
| 723 | /// delete. What was deleted. |
| 724 | pub(crate) fn delete_orphans(&self, keys: Vec<Dat>) -> Outcome<Orphans> { |
| 725 | let _hold = res!(self.db.ns_lane().hold()); |
| 726 | let found = res!(self.confirm_orphans_held(keys)); |
| 727 | for path in &found.values { |
| 728 | res!(self.remove_key(&self.value_key(path))); |
| 729 | } |
| 730 | for dir in &found.dirs { |
| 731 | res!(self.remove_key(&self.index_key(dir))); |
| 732 | } |
| 733 | Ok(found) |
| 734 | } |
| 735 | |
| 736 | fn confirm_orphans_held(&self, keys: Vec<Dat>) -> Outcome<Orphans> { |
| 737 | let vpre = fmt!("ns:{}:v:", self.space); |
| 738 | let dpre = fmt!("ns:{}:d:", self.space); |
| 739 | let mut seen: BTreeMap<String, Option<Index>> = BTreeMap::new(); |
| 740 | let mut out = Orphans::default(); |
| 741 | for key in keys { |
| 742 | let s = match &key { |
| 743 | Dat::Str(s) => s, |
| 744 | _ => continue, |
| 745 | }; |
| 746 | if let Some(path) = s.strip_prefix(&vpre) { |
| 747 | if res!(self.db.api().contains_wait(&key, None)) |
| 748 | && !res!(self.linked(path, false, &mut seen)) |
| 749 | { |
| 750 | out.values.push(path.to_string()); |
| 751 | } |
| 752 | } else if let Some(dir) = s.strip_prefix(&dpre) { |
| 753 | if !dir.is_empty() |
| 754 | && res!(self.db.api().contains_wait(&key, None)) |
| 755 | && !res!(self.linked(dir, true, &mut seen)) |
| 756 | { |
| 757 | out.dirs.push(dir.to_string()); |
| 758 | } |
| 759 | } |
| 760 | } |
| 761 | Ok(out) |
| 762 | } |
| 763 | |
| 764 | // Whether every directory from the root down lists the next name, as the right kind. |
| 765 | fn linked(&self, path: &str, is_dir: bool, seen: &mut BTreeMap<String, Option<Index>>) |
| 766 | -> Outcome<bool> |
| 767 | { |
| 768 | if check_path(path, false).is_err() { |
| 769 | return Ok(false); |
| 770 | } |
| 771 | let parts: Vec<&str> = path.split('/').collect(); |
| 772 | let mut dir = String::new(); |
| 773 | for (i, name) in parts.iter().enumerate() { |
| 774 | if !seen.contains_key(&dir) { |
| 775 | let idx = res!(self.read_index(&dir)); |
| 776 | seen.insert(dir.clone(), idx); |
| 777 | } |
| 778 | let want_dir = i + 1 < parts.len() || is_dir; |
| 779 | match seen.get(&dir) { |
| 780 | Some(Some(idx)) => match idx.get(*name) { |
| 781 | Some(e) if e.is_dir == want_dir => (), |
| 782 | _ => return Ok(false), |
| 783 | }, |
| 784 | _ => return Ok(false), |
| 785 | } |
| 786 | dir = Self::join(&dir, name); |
| 787 | } |
| 788 | Ok(true) |
| 789 | } |
| 790 | |
| 791 | // ── Index records ──────────────────────────────────────────────────────────────────────── |
| 792 | |
| 793 | fn join(dir: &str, name: &str) -> String { |
| 794 | match (dir.is_empty(), name.is_empty()) { |
| 795 | (true, _) => name.to_string(), |
| 796 | (false, true) => dir.to_string(), |
| 797 | (false, false) => fmt!("{}/{}", dir, name), |
| 798 | } |
| 799 | } |
| 800 | |
| 801 | // What must be present for an entry to be live: a value, or a directory's index record. |
| 802 | fn backing_key(&self, path: &str, e: &Entry) -> Dat { |
| 803 | if e.is_dir { self.index_key(path) } else { self.value_key(path) } |
| 804 | } |
| 805 | |
| 806 | fn bytes_of(dat: Dat, path: &str) -> Outcome<Vec<u8>> { |
| 807 | match dat { |
| 808 | Dat::BU8(b) | Dat::BU16(b) | Dat::BU32(b) | Dat::BU64(b) => Ok(b), |
| 809 | other => Err(err!( |
| 810 | "The ns value at '{}' is not bytes: {:?}.", path, other.kind(); |
| 811 | Decode, Unexpected)), |
| 812 | } |
| 813 | } |
| 814 | |
| 815 | fn read_index(&self, dir: &str) -> Outcome<Option<Index>> { |
| 816 | let dat = match res!(self.db.api().get_wait(&self.index_key(dir), None)) { |
| 817 | None => return Ok(None), |
| 818 | Some((dat, _)) => dat, |
| 819 | }; |
| 820 | let map = match dat { |
| 821 | Dat::Map(m) => m, |
| 822 | other => return Err(err!( |
| 823 | "The ns index of '{}' is not a map: {:?}.", dir, other.kind(); |
| 824 | Decode, Unexpected)), |
| 825 | }; |
| 826 | let mut idx = Index::new(); |
| 827 | for (k, v) in map { |
| 828 | let name = match k { |
| 829 | Dat::Str(s) => s, |
| 830 | other => return Err(err!( |
| 831 | "The ns index of '{}' has a non-string name: {:?}.", dir, other.kind(); |
| 832 | Decode, Unexpected)), |
| 833 | }; |
| 834 | let e = match v { |
| 835 | Dat::Tup3(t) => match (&t[0], &t[1], &t[2]) { |
| 836 | (Dat::Bool(d), Dat::U64(s), Dat::U64(m)) => |
| 837 | Entry { is_dir: *d, size: *s, mtime_ms: *m }, |
| 838 | _ => return Err(err!( |
| 839 | "The ns index of '{}' has a malformed entry for '{}'.", dir, name; |
| 840 | Decode, Unexpected)), |
| 841 | }, |
| 842 | other => return Err(err!( |
| 843 | "The ns index of '{}' has a {:?} entry for '{}'.", dir, other.kind(), name; |
| 844 | Decode, Unexpected)), |
| 845 | }; |
| 846 | idx.insert(name, e); |
| 847 | } |
| 848 | Ok(Some(idx)) |
| 849 | } |
| 850 | |
| 851 | fn write_index(&self, dir: &str, idx: &Index) -> Outcome<()> { |
| 852 | let mut map = DaticleMap::new(); |
| 853 | for (name, e) in idx { |
| 854 | map.insert( |
| 855 | Dat::Str(name.clone()), |
| 856 | Dat::Tup3(Box::new([Dat::Bool(e.is_dir), Dat::U64(e.size), Dat::U64(e.mtime_ms)])), |
| 857 | ); |
| 858 | } |
| 859 | let resp = res!(self.db.api().store(self.index_key(dir), Dat::Map(map), self.user)); |
| 860 | res!(resp.recv_store_ack()); |
| 861 | Ok(()) |
| 862 | } |
| 863 | } |