Lines Matching full:we
29 * "cached" data is always dirty. The end result is that we get thin
38 * operation all of our available space will be allocated. Thus, we need an
39 * efficient way of deleting things from the cache so we can write new things to
42 * To do this, we first divide the cache device up into buckets. A bucket is the
51 * The priority is used to implement an LRU. We reset a bucket's priority when
52 * we allocate it or on cache it, and every so often we decrement the priority
59 * we have to do is increment its gen (and write its new gen to disk; we batch
62 * Bcache is entirely COW - we never write twice to a bucket, even buckets that
110 * Our unit of allocation is a bucket, and we can't arbitrarily allocate and
113 * (If buckets are really big we'll only use part of the bucket for a btree node
115 * btree node. I'd actually like to change this, but for now we rely on the
116 * bucket's gen for deleting btree nodes when we rewrite/split a node.)
121 * The way this is solved is that btree nodes are internally log structured; we
123 * means each set of keys we write is sorted, but the node is not.
125 * We maintain this log structure in memory - keeping 1Mb of keys sorted would
126 * be expensive, and we have to distinguish between the keys we have written and
127 * the keys we haven't. So to do a lookup in a btree node, we have to search
128 * each sorted set. But we do merge written sets together lazily, so the cost of
139 * We can't just invalidate any bucket - it might contain dirty data or
154 * Bcache's journal is not necessary for consistency; we always strictly
160 * Rather, the journal is purely a performance optimization; we can't complete a
161 * write until we've updated the index on disk, otherwise the cache would be
163 * journal, on random write workloads we constantly have to update all the leaf
168 * The journal is just a log of keys we've inserted; on startup we just reinsert
169 * all the keys in the open journal entries. That means that when we're updating
170 * a node in the btree, we can wait until a 4k block of keys fills up before
173 * For simplicity, we only journal updates to leaf nodes; updates to parent
237 * Beginning and end of range in rb tree - so that we can skip taking
238 * lock and checking the rb tree when we need to check for overlapping
313 /* Refcount on the cache set. Always nonzero when we're caching. */
435 * When allocating new buckets, prio_write() gets first dibs - since we
437 * prio_last_buckets[] contains the last buckets we wrote priorities to
448 * cached data in them, and we can't reuse them until after we write
464 * If nonzero, we know we aren't going to find any buckets to invalidate
465 * until a gc finishes - otherwise we could pointlessly burn a ton of
497 * CACHE_SET_UNREGISTERING means we're not just shutting down, we're detaching
501 * CACHE_SET_STOPPING always gets set first when we're closing down a cache set;
502 * we'll continue to run normally for awhile with CACHE_SET_STOPPING set (i.e.
569 * We never free a struct btree, except on shutdown - we just put it on
576 * btree_cache_freeable effectively is a small cache - we use it because
589 * If we need to allocate memory for a new btree node and that
590 * allocation fails, we can cannibalize another node in the btree cache
599 * When we free a btree node, we increment the gen of the bucket the
600 * node is in - but we can't rewrite the prios and gens until we
601 * finished whatever it is we were doing, otherwise after a crash the
602 * btree node would be freed but for say a split, we might not have the
612 * For any bio we don't skip we subtract the number of sectors from
613 * rescale; when it hits 0 we rescale all the bucket priorities.
621 * When we invalidate buckets, we use both the priority and the amount
623 * those together consistently we keep track of the smallest nonzero
629 * max(gen - last_gc) for all buckets. When it gets too big we have to
698 /* List of buckets we're currently writing data to */
751 * We only need pad = 3 here because we only ever carry around a
752 * single pointer - i.e. the pointer we're doing io to/from.