Development plan and design decisions

[SUPERCILEX]

Development plan

Phase 1

Put everything in one bigass crate and commit shitty code. The goal is to get the core functionality 100% working. Develop with a normal cosmic iced app (or just a truly normal iced app if it turns out cosmic apps require the DE to be running).

Phase 2

De-shittify the code, implement the fastest algorithms, cleanup, etc.

Phase 3

Split the core algorithms and data structures into their own crate. There will probably be three crates: core, applet, and app. We can probably call them Gerono because the clipboard is like an hourglass in the sense that all apps will (implicitly) write to it and then any app can get data out. The clipboard is a pinch point.

Phase 4

Final polish, figure out distribution, how to ship, etc.

Design decisions

• Database compression
  • No. Use bcachefs and enable compression on the data folder.
• Database encoding
  • Why are we special? As in why not use sqlite? Copying to clipboard has a distinct usage pattern wherein the data is almost exclusively append-only. This means we can provide significant performance and efficiency improvements by implementing our own database format.
  • Use SoftbearStudios/bitcode and implement streaming support: https://github.com/SoftbearStudios/bitcode/issues/6. Implement the same log structure used for GCH. Use encoding hints liberally. A consequence of using this lib is that any change to the data types (like adding an enum) is backwards incompatible, so we'll need a migration story. Make the first byte of each shard be a version number.
• Shard the database across files, trying to match the number of files to the number of cores in the machine, with some minimum file size (maybe 8MB?) before starting to shard. This means we'll be able to load the database into memory at max speed. Also use a max shard size (maybe 128MB?) so any shard-wide ops aren't horrible to do (e.g. database migration only needs to occur on shards that are modified, so most of them can be untouched, but the ones we do touch probably shouldn't be humongous).
  • TODO think about how and when to shard. Ideally have an old and new folder, with an atomic rename to commit the changes. Use hard links to migrate shards that didn't change. Or maybe since most shards won't change, just have an old and new shard file and do the atomic rename for those files?
• Only load into memory and display in the UI the clipboard entries for the latest shard. Realistically no one is going to be scrolling through thousands of clipboard entries. For search, stream through all the other shards. Search works like in https://github.com/SUPERCILEX/gnome-clipboard-history where you do both a plaintext match and a regex match (using BurntSushi's stuff of course).
• Make IDs u32s and be local per shard (as long as the max shard size is less than 4GBs we can't run out of address space so no need to worry about overflow). This means if you delete something in another shard, we'll put the delete in that shard. Move or favoriting will require copying the data to the current shard (which is what you want anyway since the item is hot and should be loaded as part of the single-shard init).
• TODO We need some way to know for compaction if a shard is dirty for compaction. Maybe a marker file? Maybe rename the shard file? Maybe a single database metadata file? How to ensure atomicity/consistency?
• Can we mmap the shard? No because compaction might move bytes around and append support is iffy AFAIK. So loading a shard will consist of streaming through the file, parsing each entry into a Vec and allocating a string using some slab library (actually maybe that doesn't help? Need to check the implementation. Ideally the allocator backed with a stack).
• For large strings, don't actually store them in the shard (how about if they're 65K bytes or longer so we can use a u16 string len) and instead use the non-plaintext mime type handling.
• Support arbitrary mime types by saving their data somewhere outside the log.
  • TODO figure out a design for this. Use one file per entry because we want people to be able to see their copied images for example. Maybe use mime type as directory name?
• TODO can we support multiple writers? That probably requires a client/server model which I really don't like. At the very least it'd be nice to be able to know we'll corrupt things if we write. Use a lock file?
• In memory, since we're storing entries in a Vec we need some way to support moves and deletes. The most cache efficient way to do this will be to use tombstones. So just slap a tombstone in place of the entry and append to the front of the list. Then compaction will take care of making sure the vec doesn't grow too big.
• Tooling: we should have a cli that can read shard files (input is a list).
  • Stats command which shows you stats on the items in the shard.
  • Export command that supports human output and json output.
  • Debug command that analyses byte offsets etc.
  • Migrate command that concerts from GCH to our format. Also support Clipboard Indicator and maybe if I'm feeling bold.
  • Generate command which creates pseudo random shards for perf testing.
• A ratui client would be cool to have. Probs the easiest to start with for development.
• TODO consistency model. Figure out when to fsync changes to disk. Pretty sure we want to let normal copies go through without a sync, but maybe compaction should sync? There should be an fsync on application close.
• TODO Crash resilience. Think about how the format can break and how we can recover gracefully.

---

Stats from my clipboard:

Stats: Stats {
    raw: RawStats {
        num_entries: 5001,
        total_str_bytes: 3701123,
        ops: OpCountStats {
            num_save_texts: 5130,
            num_deletes: 129,
            num_favorites: 1,
            num_unfavorites: 0,
            num_moves: 25,
        },
    },
    computed: ComputedStats {
        mean_entry_length: 721.4664717348928,
        median_entry_length: 18,
        min_entry_length: 1,
        max_entry_length: 585304,
    },
}

import matplotlib.pyplot as plt
import numpy as np

def generate_histogram(file_path):
    # Read data from the file
    with open(file_path, 'r') as file:
        numbers = [float(line.strip()) for line in file]

    # Calculate the minimum and maximum powers of 2
    min_power = int(np.floor(np.log2(min(numbers))))
    max_power = int(np.ceil(np.log2(max(numbers))))

    # Create a histogram with bins as powers of 2
    bins = 2 ** np.arange(min_power, max_power + 1)
    hist = plt.hist(numbers, bins=bins, color='blue', edgecolor='black')

    # Add labels and title
    plt.xscale('log', base=2)
    plt.xlabel('Value (log base 2)')
    plt.ylabel('Frequency')
    plt.title('Histogram of entry lengths')

    # Modify x-axis labels to show bucket ranges
    bin_ranges = [f'2^{int(np.log2(bins[i]))}' for i in range(len(bins))]
    plt.xticks(bins, bin_ranges, rotation='vertical')

    # Add space at the bottom of the plot
    plt.subplots_adjust(bottom=0.15)

    # Display the histogram
    plt.savefig("stats.png", dpi=300)

file_path = 'tmp.txt'
generate_histogram(file_path)

[SUPERCILEX]

Prior art:

• https://github.com/hluk/CopyQ
  • Doesn't support copying images
• https://github.com/Slackadays/Clipboard
  • Could be cool to support a terminal interface
• https://github.com/xrelkd/clipcat
  • Seems both too simple from a user perspective and too complex from an implementation standpoint. Implements append correctly-ish https://github.com/xrelkd/clipcat/blob/314eeb023398693b9979250a8593b87375c6679e/crates/server/src/history/driver/fs/mod.rs#L222-L227 but I don't see a removal mechanism anywhere in that file and it seems like that data isn't even saved anywhere? https://github.com/xrelkd/clipcat/blob/314eeb023398693b9979250a8593b87375c6679e/crates/server/src/manager/mod.rs#L182-L199 Looks like there's just a final compaction on shutdown? https://github.com/xrelkd/clipcat/blob/314eeb023398693b9979250a8593b87375c6679e/crates/server/src/lib.rs#L528 Wat? That's crazy.
• https://github.com/Keruspe/GPaste
  • The most serious competitor. Easily the de facto linux clipboard manager.
  • Seems like it uses XML? https://github.com/Keruspe/GPaste/blob/436c4b9a344cd506e2defb1c4682c6713c4c7492/src/daemon/tmp/gpaste-file-backend.c#L50 Ouch.

---

This is kind of exciting, I think there's an opportunity to provide a world-class clipboard manager that beats everything else out there in terms of performance and core functionality (as long as we support arbitrary mime types).

Long term, we could support running arbitrary commands on copy, multiple front-ends, and other fancy features.

[SUPERCILEX]

Oooooh, I just had a very interesting idea: instead of combining metadata and data in the same file (which means mmap doesn't help because you still have to stream through the entire file), what if you split data and metadata into their own files? Then metadata contains fat pointers to the data file which can be mmaped. Similarly if we make metadata enums take precisely the same amount of space, then we can also mmap metadata and do simple offset calculations to transmute some bytes into an enum. This makes compaction much more efficient as we don't necessarily have to move any data around.

In essences, this means we're writing a memory allocator because the standard optimizations apply. Instead of compaction, you could keep a free list. Instead of everything in one file, you could keep fixed block sizes around. I think I like this because it should make sharding the log files much faster and basically unnecessary for at least the first few years of people using the clipboard as an 8MiB file can hold ~250K 32 byte entries which would take ~7 years to fill up assuming you copied 100 things a day.

We have two constraints:

• Adding a new entry has to be instant.
• Deleting an entry has to support compaction without ending the world. So for example storing all the data in a single file is a no-no because if you have a gig's worth of clipboard entries and delete something near the beginning, that means shifting nearly the entire gig up. In theory you could get fancy and hook into the file system extents to not move any data, but then that leaves an N block sized hole which is pretty useless for other files and adds a seek for hard drives. So basically the file system will eventually have to move that data around for you anyway.

This leads to the following solution based on my clipboard data:

• Use bucket allocation files for entries with powers of 2 sizes from 2^2-2^12.
• Allocate a new file for anything larger than a logical disk sector size (4096).

[SUPERCILEX]

mmap + append sounds like a big PITA sadly. Might be doable with mmaping more than is in the file or using ftruncate/fallocate. Though maybe we could just avoid ever remapping?

Also probs would need a separate metadata file for favorites if we're not going to read the entire log (which should probably be the goal as this gives us O(1) startup). Though maybe that's not worth it and we should just allocate a huge vec on startup? I don't like the fact that it forces us to hold that stuff in memory rather than letting the OS decide when to load disk pages in.

The deal with deletions is that they're implicitly continuous. If you've reached the maximum number of items/clipboard size, then every entry addition deletes an entry. Since it'll delete the oldest one, that's kind of our worst case scenario for the log because we have to shift everything back. So maybe we should actually bounce back and forth between two logs? Yeah actually I think this is the right solution. If a user says "I want my maxnum items to be 1M", then `lim(t -> infinity) num_items = 1_000_000`. Wait a sec, why not a ring buffer? The reason I couldn't do that before is because data was stored with metadata, but if every entry is the same size, then I can make the log a ring buffer!!! Fuckin genius.

Ok, so the idea would be that you write to a log file until you hit the max num elems and then just wrap and smash whatever's in the back. We'll need a header which notes the write head? I don't think we ever actually advance the back pointer explicitly?

Ops:

• Add: easy, just a bump allocator with smash on OOM.
• Move
  • Can support move to end by pretending like it's an add + tombstone the old.
  • Can support left/right swaps by literally swapping adjacent entries
  • Obviates the need for a MOVE op and enables only reading the end of the log.
• Favorite: needs to be in a separate file to be excluded from the smash on OOM behavior of the ring allocator.

---

Random thoughts on the client/server stuff: it would be really cool to have this be the defacto clipboard manager for linux as this design is shaping up to be world class. I think we can have the server create a delete-on-close named pipe for reading commands. Clients open their own named pipes (as it looks like there's no good way to send file descriptors around, see https://man7.org/linux/man-pages/man2/pidfd_getfd.2.html) and send the server a message with the location of the file descriptor. It's then the server's job to broadcast messages like "new clipboard item" and reply to specific pipes for individual requests like "give me this item". The problem of course with client-server architectures is that it's super inefficient for clients to read data. Here's a stupid idea: what if I just run the client inside the server process? So maybe the server is a main loop with a switch between different GUIs and when you shut down a GUI it just waits to be told to open the next one? Doesn't really work for terminals where you need the server to run outside the terminal process. So maybe you keep the named pipes idea and just have clients do an initial read-only load of the data from the log file and then everything else it gets is replies from the server that say the data is located here, go look it up yourself which would mean mmapping all the data files. And I guess the server needs to notify clients when it should remap files because they grew. Could work and be reasonable efficient. Also for the applet is might actually make sense to not bother receiving data from the server and just do a load from the log each time it is opened. The theory there being that you can't copy stuff while the applet is open (so we don't need to subscribe to changes) and while the applet is closed we don't want it wasting cycles doing GUI stuff anyway. Any user action could be reflected in the UI as a lie that's immediately processed but asynchronously handled by the server. Honestly this seems like a reasonable strategy for all the GUIs? Like do we really care if you're watching the GUI as you copy stuff? Actually yeah maybe we do. So it could be a hybrid thing where you close your pipe when the user isn't looking and then open it to subscribe to events while the UI is open.

[SUPERCILEX]

Actually unix domain sockets are precisely designed for the client/server stuff I want to do and have the same performance according to some random benchmark, so just use that instead of my half-assed multiple pipe nonsense: https://man7.org/linux/man-pages/man7/unix.7.html. Still doesn't solve the problem of not wanting to send data over the channel.

[SUPERCILEX]

Ok so there's also sysv: https://man7.org/linux/man-pages/man7/sysvipc.7.html. Basically it sounds like I can do anything I want: move FDs around processes, shared memory between them, and synchronize their actions. Should free up the design space considerably.

[SUPERCILEX]

Title for the announcement:

• Short: Ringboard: the infinitely scalable clipboard manager for Linux
• Long: Ringboard: the infinitely scalable clipboard manager for Linux backed by a high-performance arena allocated database

Key claim: memory usage is O(1) for normal usage, so you're only limited by disk space (well that and the ID limits, but that's easily increased if it was something we cared about).

Server

The server is a (mostly) single-threaded application as everything we are doing is designed to minimize latency and maximize efficiency rather than worry about throughput. The server is implemented as a connection oriented (SOCK_SEQPACKET) unix domain socket with a core loop that simply processes requests from clients and issues syscalls using io_uring. We will tell people that old kernels and non-linux kernels are not officially supported, though PRs to do blocking I/O may be considered for acceptance.

On a new connection the server tells the client its version. The client checks for an exact match and shuts down if its version doesn't match the server's

The server's goal is to be the one and only place where data is written. On startup, the first thing it will do is open the ring file and acquire an exclusive lock (https://man7.org/linux/man-pages/man2/flock.2.html). Clients only ever open files in read-only mode, so they don't care about the lock. It's only used to prevent concurrent server instances.

The server will be backend agnostic (so wayland and x11) gated by feature flags. When a feature isn't enabled, the implementation returns an error upon creation which a unifying impl uses for broadcast/merging purposes. Looks like this:

struct AllBackends {
  a: Option<BackendA>,
  b: Option<BackendB>,
}

impl Backend for AllBackends {
  // Impl with Option::map and error tuples? Or maybe handle errors internally? Maybe closures?
}

// Maybe use https://docs.rs/arrayvec/latest/arrayvec/struct.ArrayVec.html as message buffer (actually nevermind because clients are backends now)
// New idea: make every client a backend since it can also send add events and request content

Nope, the backends should be in a list as clients and wayland are treated the same.

Each backend will need to return a file descriptor for io_uring to wait on. For wayland, this should be pretty easy. Haven't looked into X11 but worst case scenario a backend can start a thread and do a blocking loop which writes to an in-memory pipe that is read by io_uring. Not very efficient, but it'll cleanly handle back pressure and message passing.

All files that need to be read will be mmaped into the client and server as read-only. Writes will happen through normal write syscalls which is supposed to be coherent (and note that multiple processes mmapping the same file is also coherent as the pages are simply shared across processes). We cannot write directly to mmapped regions because there is no guarantee on when the data will be written back to disk which means we would need our own https://man7.org/linux/man-pages/man2/msync.2.html flushing policy and that sounds unpleasant. Also I doubt performance will be good assuming writes trigger page faults. With normal write syscalls, all you should get is cache flushes for the affected addresses which in practice means no overhead at all since adding a clipboard entry shouldn't involve reading and most of the time clients won't be active so no data will be in the cpu caches. Or maybe that assumption is wrong and I'd need to run perf tracking tlb flushes to check, but the other issue with not using mmap for reading is that then everything needs to be loaded into individually malloced buffers (String) and that's definitely terrible for performance.

Entry encoding:

struct Entry {
  bucket_index: u20,
  size: u12,
}

• Size of zero means this is NOT a bucket allocation. In that case, bucket_index has some bit set (don't care which one) to avoid all-zeros.
  • The id of the item for directory naming purposes and retrieval is implicit and permanently baked into its position in the ring buffer. The entry's position is immutable for the entirety of its lifetime, including garbage collection. The tradeoff here is that we won't precisely respect the user's max items, as in if they deleted something in the middle of the ring buffer we won't skip over intermediate allocated objects to fill that hole, we'll just keep marching onwards.
• Otherwise, the data was allocated in a bucket and size is the item's size in bytes while the bucket_index is where in the bucket the item was allocated.
  • The bucket to use is implicitly determined from the item's size.
• The maximum number of items is implicit in the size of the ring buffer.
• An all-zero entry is unallocated.

Ring buffer header:

struct Header {
  version: u8,
  write_head: u32,
}

Process for adding a new clipboard entry:

• io_uring notifies us that an fd did something.
• Notify the corresponding backend.
• The backend parses the message, sees that it's an Add type and returns the Add command.
• All data communication happens over file descriptors, so the client or wayland or x11 will need to have given us a file descriptor from which to read the data.
• The ring's write head is checked and used to find the next ring buffer entry to write into (bump allocator).
  • If the entry is empty, simply allocate the clipboard data and write a new entry into the ring buffer. Use pwritev to simultaneously update the entry and write head.
  • If the entry contains data, trigger a remove op before doing a normal add.
• Notify all backends of the addition with the ID of the entry.

Delete an item:

• Zero out the entry.
• If a bucket allocation, simply add the index to the free list.
• If a file allocation, delete the directory manually by removing the known files in the directory and then the directory itself (saves us from iterating through the directory).

Move item:

• Delete the target item (or do nothing if it's already unallocated).
• Do a swap.

Swap items:

• Swap the entries.
• Do a RENAME_EXCHANGE if the items are both not buckets: https://man7.org/linux/man-pages/man2/rename.2.html

(Un)Favorite item:

• Favorites are implemented as just another instance of a ring buffer, but with a different max number of items.
• Changing the status delete and adds the entry in the appropriate buffers.
• The entry ID has its high bit set to 1 if it's a normal entry and 0 if it's a favorite so non-bucket items don't conflict. 1 was chosen for normal so that if the user looks at their data dir favorites will be sorted at the top.

Changing the max number of items:

• Grow: do nothing but remap. This means we'll continue to nuke old items until we cycle around. I think this is fine and saves the very expensive data movement costs.
• Shrink (check that we actually wrote past the new limit before doing this): stream through the entire ring (starting at the head) copying entries to a new ring. Entries larger than 4096 need to have their data moved to their new ring IDs. The new head is just zero as the items are added in reverse order.
  • Create hard links of all the files into a new data.tmp/ to avoid conflicts.
  • Rename the existing data directory to data.old/.
  • Rename the new ring to overwrite the existing one.
  • Delete data.old with fuc.
  • This is crash safe because we never modify the original data, and rename the existing data directory upon completion which means a hard crash can just finish this operation to complete recovery. Otherwise on recovery we discard all the data and start over.

Nuke (aka delete everything):

• Using https://github.com/SUPERCILEX/fuc/tree/master/fuc_engine, delete the data directory.
• Write zero to the write header.
• ftruncate to header size the ring buffers.

Search:

• This is pretty cool: we don't need to use any memory and it's still as fast as can be without indexing!
• Sort the free lists (descending even though that's annoying as it's better for garbage collection)
• Stream through every bucket on its own thread (skipping buckets whose size is smaller than the query)
  • Skip slots on the free list
  • Find matching entries though a plain text search or a regex search (option provided by user on query time, togglable with Alt+X). Stop on NUL byte.
• On a seperate thread do a search on the non-bucket items by using my rustix dir iterator and looking for text-like mime types.
  • unshare the fd table on this thread.
• On yet another thread, stream through the favorites ring noting bucket allocations in a set.
  • Once this is done, update any already visible search entries and keep the set on standby for new entries.
• Show these entries to the user as they arrive (with a std::mpsc channel that will be replaced by lockness)
  • If the user performs an action on one of the items, do a reverse search on the ring buffer for that bucket index (unless it's a favorite of course or it's a non-bucket item in which case we already have its entry index/id)

Extra commands for the client:

• Incoherent/coherent: clear all visible items and allow peeking when done. This is needed for garbage collection as the client's references may be invalidated.
• Reboot: close the ring buffers and reload them. This is needed for max item shrinking when we do a full re-layout of the data by replacing the ring buffer files.

Extra commands for the server:

• Garbage collect: explicitly run gc.
• Reload settings.

How data allocation works:

• The ring buffer is mmapped to the size of max items (and space for the header) so that we never need to remap it.
• A maximum of 2^20 entries are allowed (see entry encoding for why).
  • Actually, 2^20-1: let's give ourselves an escape hatch to indicate that the next entry is part of the current one so we can have more bits in case that's needed for something.
• Create bucket files for entries with sizes up to and including powers of 2 in [2, 12]. Except for 2^12 which actually only allows up to 4095 (see entry encoding for why).
• If data is larger than or equal to 4096, allocate it by ID (the ring buffer position)
  • Create a directory named ID.
  • The directory contains a data file and a metadata file. The metadata file includes the mime type(s) of the file.
• If the data index is beyond the mmapped region, it means the file has grown, so do a statx call and remap the region.
• Use copy_file_range to write the data.
  • Also write a NUL byte to the end of the data (unless the data takes up the entire space) for search
• The free lists are stored in-memory until shutdown, so allocate from there if we have a free item.
  • On startup (if the lock file doesn't exist), read the free lists encoded with bincode.
  • If the shutdown was unclean, stream through the entire ring buffer and build up the free lists on the fly.
  • Build an allocation bit vector and take the compliment to produce free indices.
  • On shutdown, write the free lists before deleting the lock file.
  • If the amount of free data exceeds say 50% of the allocated data, we run garbage collection.
  • Ideally we'd do continuous garbage collection, but that requires a reverse index.
  • Garbage collection is implement as follows (note that the multiple ring streams for different purposes should be combined into a single pass in the real code):
    1. Do "pre gc" to deduplicate entries
    2. Build a HashMap of non-bucket entry sizes to Vec.
    3. mmap in the bucket files.
    4. Built a BTreeSet of every single bucket entry's byte slices.
    5. Stream though the rings in newest to oldest order, deleting entries that we've already seen. If we have a non-bucket entry, check to see if its size matches somebody else and in that case mmap the two competing entries and see if they're equal.
    6. Sort the free lists (descending).
    7. Stream through the ring and build allocation lists (as VecDeque, see below) for each entry farther than the top of the free list (as in only the allocations past the holes):
    8. Go through the free and allocation lists, popping each item (which will be earlier in the file for the free list and later for the allocation list).
    9. Move the allocation to the free item and add the allocation index to the free list (binary search insert to make sure it's in the right position which isn't efficient as it requires moving elements but oh well).
    10. Trim the allocation list with the new smallest free index (free operating as we're using a VecDeque).
    11. Once either list is empty, we are fully compacted.
    12. ftruncate the file to its compacted size.
    13. Return the amount of space that was freed.

Directory structure:

• $DATA_DIR/clipboard-history/
  • server.lock:
  • Lock file to prevent multiple instances
  • Stores the PID of the owning process
  • Used to detect unclean shutdown
  • data/: folder for all data files
  • main.ring: ring buffer for normal entries
  • favorites.ring: favorites ring buffer
• $CONFIG_DIR/clipboard-history/settings.kdl
  • Example: https://github.com/pop-os/system76-scheduler/blob/master/data/config.kdl
  • Store (versioned) settings for stuff like max num items.
• $CACHE_DIR/clipboard-history/
  • server.log: file for server log messages. Opened with truncate on server startup.
• /tmp/$USER_NAME-clipboard-history
  • Unix domain socket

Random notes:

• The server only needs to mmap ring buffers as it never reads clipboard data. Clients should mmap everything.
• The default max number of items is 100K.
• The default max number of favorites is 1000.
• The server registers SIGTERM, SIGQUIT, and SIGINT signal handlers to do a clean shutdown.
  • The server creates a pipe and gives the write end to the signal handler while the read end is given to io_uring to be processed as an event like any other.
• The server automatically replaces any existing server by reading the lock file and sending a SIGTERM to it.

Resources for integrating with the clipboard

• https://github.com/JoeyEamigh/wayclip/blob/main/src/wayland/mod.rs
• https://emersion.fr/blog/2020/wayland-clipboard-drag-and-drop/
• https://github.com/quininer/x11-clipboard/blob/master/src/run.rs
• https://github.com/Smithay/wayland-rs/issues/690

GUI/TUI

Two lists side-by-side, one for favorites and one for normal items. This ensures you can have a lot of favorites without it making it annoying to access normal items. Only 100 items are loaded. If someone asks for it, maybe I could implement pagination, but in GCH I personally never use pagination and only search.

CLI

Commands:

• debug
  • stats: displays statistics about the clipboard. Include everything from GCH + number of holes in ring buffers + utilization of each bucket allocator (both raw number of free entries and computed stats) + total amount of free space + number of duplicate entries + amount of space that could be saved by running a gc + number of non-bucket entries, their size and computed mean/median/etc, a hash table of stats by mime type (excluding bucket entries so you can easily see the large plain text allocations).
  • dump -c,--contents
  • Decodes the ring buffers
  • If contents is specified, also prints the data for each entry
  • generate -n,--num-entries -m,--mean-size -s,--stddev-size path
  • Generates a random directory for benchmarking/testing purposes.
  • fuzz -n,--num-clients
  • Spam the server with randomly generated commands
• add {path,-}
  • Accepts a file path or the stdin marker and sends the server an add command for that FD
  • Prints the ID of the newly added item
• remove id
  • Sends a remove command
• move-to-front id
• swap id1 id2
• favorite id
• unfavorite id
• gc
• wipe
• reload-settings
  • The user can edit the settings config file and then execute a reload to make the server take those changes into account.
• migrate protocol
  • For example we'll offer migration from GCH and clipboard Indicator. Maybe we try gpaste?

[SUPERCILEX]

Call the project Ringboard.

[SUPERCILEX]

An entry ID is the concatenation of a tag ID and a ring ID, each 32 bits. So the full entry ID is 64 bits. This enables the architecture to seamlessly transition to tagged entries if I ever decides there's any point to doing that.

[SUPERCILEX]

Next steps:

• implement version handshake between server and client
• add logging and tracing crates
• implement allocator and make add command fully work
• use a bit vector to keep track of connected clients and their fixed file descriptors so I can loop through the clients to broadcast new copies
• ...

[SUPERCILEX]

Next steps:

• Implement all CLI commands (leave server implementation blank for the hard stuff like garbage collection).
• Add X11 and Wayland clipboard watchers.
• Finish blog post and post it in draft state.
• Start posting about the project and asking for help implementing GUIs.

[SUPERCILEX]

Dumb idea, but what if the X11/Wayland watchers are just clients? So they run in their own binaries which means I don't have to care about bloat, feature flags, performance stuff etc.

[SUPERCILEX]

Note in blog post that metadata files are fine because they're so tiny: https://www.kernel.org/doc/html/latest/filesystems/ext4/overview.html#inline-data

[SUPERCILEX]

Thoughts on error handling: to keep things simple, we assume that requests are only made by trusted code, so we don't bother validating the contents of requests. This also means we don't have to make the server resilient to bad clients and it can just shut down when something goes wrong. Basically we're cool with clients performing denial of server. However, assuming the code is trusted, we do perform error handling for dynamic values (for example to check that the ID a user asks us to move is valid).

[SUPERCILEX]

Thoughts on reading data and search:

• Add a RingReader interface that allows creating an iterator from any entry and can move back and forth. Look into all the things you're supposed to implement for iterators (size hint, fuse, double ended, etc). Iterates over raw entries, avoiding uninitialized entries is a higher level problem.
• Add an EntryReader enum. The core interface is to_file which produces a File. For non-bucket entries this is close to free, but for Bucket entries we'll need to create a tmpfile and copy_file_range the bytes into there. Offer a method on the bucket variant that returns a byte slice.
• Need to figure out how bucket resizing works. Somehow need to provide multiple shared references but take some type by value to force dropping the references at which point we can remap the file. Or maybe I can be lazy and put the original mapping in an Rc so the old references can slowly die out while the new mapping gets used. This is lame because we have to create a new mapping every time which is evil for the TLB etc. These ideas aren't mutually exclusive? I could have the painful references API and somebody else could just wrap it in an Rc I think.
• Garbage collection should take an excess bytes percentage that only triggers garbage collection if that amount of space has been wasted. So 0 always triggers and 100 triggers if we're using 2x the storage. Then search can send a garbage collection command before starting so it doesn't waste too much time searching garbage. Maybe 50%? Also how about having the param actually mean "collect garbage until wasted space is under the threshold." Then garbage collection can start with the biggest buckets and do minimal work to reclaim the big ticket items.
• Search should have a whitelist of searchable mime types so we can search html text for example.

[SUPERCILEX]

Oooooh, I'm a dumdum—instead of having to create a metadata file, I can just use extended file attributes! There's even user.mime_type already defined for this purpose: https://wiki.archlinux.org/title/Extended_attributes. Those metadata files were really getting under my skin, so this is sweet. Extended attributes are even stored inline if they're small: https://www.kernel.org/doc/html/latest/filesystems/ext4/dynamic.html#extended-attributes

[SUPERCILEX]

Next steps:

• [x] Add X11 clipboard listener client
• [x] Migrate my GCH clipboard and make the server + X11 client start on boot
  • https://www.freedesktop.org/software/systemd/man/latest/systemd.service.html
  • https://docs.rs/sd-notify/latest/sd_notify/fn.notify.html
  • Looks like I want a Type=notify service for the server. I can link in sd-notify behind a systemd feature (disabled by default, but used in docs for systemd setup). The client can just be Type=exec.
  • Restart=on-failure for both
  • https://www.freedesktop.org/software/systemd/man/latest/systemd.unit.html#
  • In the client, add Requires=server and After=server and ConditionEnvironment=XDG_SESSION_TYPE=x11. Also for both add Description=... and Documentation=a link to systemd install instructions.
  • The server should start with After=multi-user.target while the client should be After=graphical.target I think.
  • https://wiki.archlinux.org/title/Systemd#Targets
  • Check that the service starts and stops correctly, that the server runs at the login screen and that the client runs once I'm logged in.
• [x] Add deduplication
• [x] GET cli command
• [ ] Write READMEs and basic docs.
• [x] Implement startup recovery
• [x] egui skeleton app
• [x] Finish fuzzing
• [ ] Finish the blog post, cutting sections on the stuff that hasn't been implemented yet (garbage collection, configuration, etc). Make a note that those will come in a part 2 once they've been fully implemented/designed.
• Start working on egui client. The MVP is a full list of entries (https://docs.rs/egui/latest/egui/containers/scroll_area/struct.ScrollArea.html#method.show_rows), then paste to clipboard, then search, then non-text entries, then the ability to modify entries, and finally whatever polish is needed.
• See if I can get anyone interested in writing a cosmic applet and/or TUI. I think I've decided that I'm not interested in writing the other clients since I personally only need a good egui one. It'd be cool if the project takes off and other people add what they need. Otherwise, I'll have the dream clipboard for myself which is good enough.
• Once the egui client is in good shape, write about search in the blog post and make announcements, publish, yadada. At this point it's completely usable, just not fully optimal and might have missing bonus features.
• After all of that, work on finishing the remaining todos (like gc, config, etc), write a blog post about those, and then call the project done.

---

Solution to the duplicates problem:

• In DE clients, spend memory (uncapped because even if you managed to copy a million entries that's still only a few dozen MBs) to remember previously copied item hashes from this session (so no loading stuff from disk on startup, the premise being that you copy the same thing multiple times because you're working on it). Algorithm: after adding entry, load stored entry from server response ID to file and stream through DefaultHasher if 4096 bytes or less, otherwise just use length. Store these hashes in a BTreeMap (for better memory efficiency) and when x11 gives us something that was copied, apply the same hashing algorithm and send a move-to-front command to the server if an entry is found in our list.
• In garbage collection, include a deduplication pass.
• Rewrite stats command to use hashing instead of loading all entries into memory.

[SUPERCILEX]

https://www.uninformativ.de/blog/postings/2017-04-02/0/POSTING-en.html and https://github.com/linebender/druid/blob/master/druid-shell/src/backend/x11/clipboard.rs as resources for the X11 clipboard. I think we can basically use the blog post a good reference. For waiting: https://github.com/cdown/clipnotify/blob/master/clipnotify.c.

[SUPERCILEX]

For non-plain-text entries, we should add some notion of context that can be stored in extended file attributes for the UI to show. For example, if you copy a google slide, there's nothing we can show (without trying to parse Chrome's custom data format, no thanks) that will be useful. But we could ask for the X11 window title at the time of copy and save that to show in the GUI. Better than nothing.

[SUPERCILEX]

Add mut methods for EntryReader that remap as necessary. After deduplication, rewrite stats to use new technique. After X11, fuzz and then publish.

[SUPERCILEX]

Still not sure what to do about paste. There are three options:

• Play the same game as copying and write a server that accepts a paste command. Seems like a few too many servers to me.
• Write a oneshot call binary whose sole purpose in life is to paste a single ringboard entry. Seems pretty inefficient.
• Write a library linked into anything that needs the ability to paste which can be compiled with an x11 and/or wayland backend. Maybe the best idea?

[SUPERCILEX]

For deduplication it turns out you there's no point in trying to be fancy because you'd need to store the contents to avoid hash collisions, so I gave and just implemented a crappy static hash table.

[SUPERCILEX]

For change broadcasting, it occurred to me that inotify/fanotify might be useful but I can't seem to find a way to subscribe to a file range. Otherwise we could have actually used that to subscribe to entry changes plus the write head.

[SUPERCILEX]

UI ideas:

• Add a shift+? for keyboard shortcuts
• Get rid of the hover stuff and put it in a right click menu
  • Include actions: favorite, delete
  • Include info: id, mime type, content
  • Esc backs out
• Start with first row of favorites selected
  • Enter pastes to clipboard
  • Space is equivalent to right click
  • Tab cycles between selecting main and favorites (remember row index of each selection)
• Up/down arrows move between rows
• Ctrl + N selects row num (show number overlay when holding Ctrl)

[SUPERCILEX]

For search, it might be worth supporting incremental plain text search. That is, for every query the user types that is a superset of the previous query, we can search through only the existing results rather than having to perform a full database search again. Furthermore, we can start searching each of these results at the saved start location of the query result (minus however many prefix characters were added in the superset query). This would basically make subsequent searches instant as it's just confirming whether or not the newly expanded query still matches rather than finding the query location all over again.

[SUPERCILEX]

Closing in favor of new issues.

[SUPERCILEX]

For pasting I decided the library is the right approach because it allows building a daemon (that uses the library) if it turns out that's what we want.

[SUPERCILEX]

I looked into adding migrations from https://github.com/hluk/CopyQ and https://github.com/Slackadays/Clipboard. CopyQ uses a binary format and I don't want to have to compile C++ to be able to build our CLI so that's not doable. Slackadays's clipboard defaults to being transients and only supports files or single entries from the command line, so I'm guessing most people don't actually store long-term history in there.

[SUPERCILEX]

Ok I changed my mind about pasting. The problem with in-process pasting is that if the UI wants to exit immediately after pasting you're screwed because you need to wait for someone to bite (the compositor should immediately, but who knows) and then you can't offer good pasting services like target selection. One option is to fork on paste but if you're spawning a process on paste anyway, might was well run a paste server. Then it occurred to me that the watcher servers already have connections to x11/wayland so why not re-use those? They'll just spin up a socket that accepts files to offer as paste.