Oregami
Repositories/oxedyne/fe2o3

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
42use crate::{
43 O3db,
44 comm::response::Wait,
45 test::hooks::{
46 self,
47 NsStep,
48 NsTear,
49 },
50};
51
52use oxedyne_fe2o3_core::prelude::*;
53use oxedyne_fe2o3_iop_crypto::enc::Encrypter;
54use oxedyne_fe2o3_iop_hash::{
55 api::Hasher,
56 csum::Checksummer,
57};
58use oxedyne_fe2o3_jdat::{
59 prelude::*,
60 id::NumIdDat,
61};
62
63use 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)]
84pub struct Lane {
85 turn: Mutex<Turn>,
86 moved: Condvar,
87}
88
89#[derive(Debug, Default)]
90struct 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)]
98pub(crate) struct LaneHold<'a> {
99 lane: &'a Lane,
100}
101
102impl 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
128impl 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)]
143pub 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)]
151pub 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)]
160pub struct Orphans {
161 pub values: Vec<String>, // paths
162 pub dirs: Vec<String>, // paths
163}
164
165pub use crate::sweep::ns_orphans as orphans;
166pub use crate::sweep::ns_sweep_orphans as sweep_orphans;
167
168type Index = BTreeMap<String, Entry>;
169
170pub 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.
178fn 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.
186fn 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`].
204pub 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
217impl<
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}