danw@181: The repo file format / razor_set data structure danw@181: ----------------------------------------------- danw@181: danw@181: The repo starts with a header, containing some number of sections, danw@181: terminated by a section with type 0: danw@181: danw@181: struct razor_set_header { danw@181: uint32_t magic; danw@181: uint32_t version; danw@181: struct razor_set_section sections[0]; danw@181: }; danw@181: danw@181: struct razor_set_section { danw@181: uint32_t type; danw@181: uint32_t offset; danw@181: uint32_t size; danw@181: }; danw@181: danw@181: razor_set_open() mmaps the repo file, and creates a struct razor_set: danw@181: danw@181: struct razor_set { danw@181: struct array string_pool; danw@181: struct array packages; danw@181: struct array properties; danw@181: struct array files; danw@181: struct array package_pool; danw@181: struct array property_pool; danw@181: struct array file_pool; danw@181: struct razor_set_header *header; danw@181: }; danw@181: danw@181: by finding the sections with those IDs and creating "struct array"s danw@181: pointing to the right places in the mmapped data. (This is the only danw@181: processing needed when reading in the file; everything else is used danw@181: exactly as-is.) danw@181: danw@181: danw@181: The sections danw@181: ------------ danw@181: danw@181: RAZOR_STRING_POOL danw@181: danw@181: Stores one copy of each string that appears in the repo. (At danw@181: the moment, this is: package names, package versions, property danw@181: names, property versions, and (basenames of) filenames.) The danw@181: strings are arbitrarily-sized, 0-terminated, and not in any danw@181: particular order (although the empty string always ends up danw@181: being at offset 0). danw@181: danw@181: RAZOR_PACKAGES danw@181: danw@181: Array of struct razor_package; one for each package in the danw@181: set, sorted by name. danw@181: danw@181: RAZOR_PROPERTIES danw@181: danw@181: Array of struct razor_property; one for each unique property danw@181: in the set, sorted by type, then name, then relation type (eg, danw@181: "<" or ">="), then version. (Properties with no version have danw@181: relation type RAZOR_VERSION_EQUAL, and version "".) danw@181: danw@181: RAZOR_FILES danw@181: danw@181: Array of struct razor_entry; one for each file owned by any danw@181: package in the set. The current sort order (which is subject danw@181: to change) is breadth-first, sorted by basename. So eg: /, /bin, danw@181: /dev, /etc, /bin/false, /bin/true, /dev/null, /etc/passwd. danw@181: danw@181: RAZOR_PACKAGE_POOL danw@181: danw@181: Array of struct list, with each list item containing the index danw@181: of a struct razor_package in the packages section. See the danw@181: discussion of lists below. danw@181: danw@181: RAZOR_PROPERTY_POOL danw@181: danw@181: Array of struct list, with each list item containing the index danw@181: of a struct razor_property in the properties section. See the danw@181: discussion of lists below. danw@181: danw@181: RAZOR_FILE_POOL danw@181: danw@181: Array of struct list, with each list item containing the index danw@181: of a struct razor_entry in the files section. See the danw@181: discussion of lists below. danw@181: danw@181: danw@181: Data types danw@181: ---------- danw@181: Note that the exact layout of bits involves some historical accidents. danw@181: (Particularly the fact that the "name" field in most structs loses its danw@181: high bits to a flags field.) danw@181: danw@181: struct list_head danw@181: uint list_ptr : 24; danw@181: uint flags : 8; danw@181: danw@181: struct list danw@181: uint data : 24; danw@181: uint flags : 8; danw@181: danw@181: Used to store lists of package, property, or file IDs. "struct danw@181: list_head" stores the head of the list, which points to one or danw@181: more "struct list"s in the appropriate "pool" section. danw@181: ("struct list" should probably be called "struct list_item".) danw@181: danw@181: "list_first(&head, &pool)" returns a "struct list *" pointing danw@181: to the first element of the list (or NULL for an empty list), danw@181: and "list_next(list)" will return successive elements, until danw@181: NULL is returned. Each "list->data" contains the index of a danw@181: package, property, or file in the corresponding section of the danw@181: set. danw@181: danw@181: Peeking underneath the abstraction, a list_head's "flags" is danw@181: 0xff if the list is empty, 0x80 if it contains a single danw@181: element, or 0x00 if it contains more than one element. In the danw@181: single-element case, that element is actually stored in the danw@181: list_head directly rather than being stored in a pool (and so danw@181: list_first() just casts the list_head* to a list* and returns danw@181: it). For multi-element lists, list_ptr is the index in the danw@181: pool of the first element of this list; the list continues danw@181: through successive elements of the pool until one with danw@181: non-zero flags is reached, indicating the end of the list. danw@181: danw@181: struct razor_package danw@181: uint name : 24; danw@181: uint flags : 8; danw@181: uint version : 32; danw@181: struct list_head properties; danw@181: struct list_head files; danw@181: danw@181: name and version are indexes into string_pool. properties is a danw@181: list of all of the package's properties, and files is a list danw@181: of its files. flags is currently only used during razor_set danw@181: merging, to keep track of which set a package came from. danw@181: danw@181: struct razor_property danw@181: uint name : 24; danw@181: uint flags : 6; danw@181: uint type : 2; danw@181: uint relation : 32; danw@181: uint version : 32; danw@181: struct list_head packages; danw@181: danw@181: name and version are indexes into string_pool. type is an enum danw@181: razor_property_type (eg, RAZOR_PROPERTY_REQUIRES), and danw@181: relation is an enum razor_version_relation (eg, danw@181: RAZOR_VERSION_GREATER_OR_EQUAL). packages is a list of the danw@181: packages that have this property. flags is currently unused. danw@181: danw@181: struct razor_entry danw@181: uint name : 24; danw@181: uint flags : 8; danw@181: uint start : 32; danw@181: struct list_head packages; danw@181: danw@181: name is an index into string_pool, giving the basename of the danw@181: file. start is either 0, or an index pointing to another danw@181: razor_entry that is the first child of this entry (for a danw@181: non-empty directory). (Entry 0 is always the root of the tree, danw@181: so no entry could have entry 0 as a child.) flags is 0x80 danw@181: (RAZOR_ENTRY_LAST) if an entry is the last entry in its danw@181: directory. Otherwise it is 0. danw@181: danw@181: Note that given a pointer to a struct_razor_entry (eg, from a danw@181: package's "files" list), there is no way to reconstruct its danw@181: full name without walking the entire files array up to that danw@181: point. Because of this and other problems (fix_file_map()), it danw@181: seems like razor_entry should be modified to include a pointer danw@181: to its parent. (Storing full paths instead of just basenames danw@181: would also fix this problem, but that would use much more danw@181: memory.)