git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 12/19] read-cache: read index-v5

From
Duy Nguyen <pclouds@gmail.com>
Date
Jul 14, 2013, 04:42 UTC
Message-ID
<CACsJy8C6HRCYMR3Q=j-D=2kgzvA7=0tauSnwrjpXzSPZWe+VZw@mail.gmail.com>
In-Reply-To
<1373650024-3001-13-git-send-email-t.gummerer@gmail.com>
On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer <t.gummerer@gmail.com> wrote:
Show 41 quoted lines
> +struct directory_entry {
> +       struct directory_entry *next;
> +       struct directory_entry *next_hash;
> +       struct cache_entry *ce;
> +       struct cache_entry *ce_last;
> +       struct conflict_entry *conflict;
> +       struct conflict_entry *conflict_last;
> +       unsigned int conflict_size;
> +       unsigned int de_foffset;
> +       unsigned int de_cr;
> +       unsigned int de_ncr;
> +       unsigned int de_nsubtrees;
> +       unsigned int de_nfiles;
> +       unsigned int de_nentries;
> +       unsigned char sha1[20];
> +       unsigned short de_flags;
> +       unsigned int de_pathlen;
> +       char pathname[FLEX_ARRAY];
> +};
> +
> +struct conflict_part {
> +       struct conflict_part *next;
> +       unsigned short flags;
> +       unsigned short entry_mode;
> +       unsigned char sha1[20];
> +};
> +
> +struct conflict_entry {
> +       struct conflict_entry *next;
> +       unsigned int nfileconflicts;
> +       struct conflict_part *entries;
> +       unsigned int namelen;
> +       unsigned int pathlen;
> +       char name[FLEX_ARRAY];
> +};
> +
> +struct ondisk_conflict_part {
> +       unsigned short flags;
> +       unsigned short entry_mode;
> +       unsigned char sha1[20];
> +};
These new structs should probably be in read-cache-v5.c, or read-cache.h
>  #define cache_entry_size(len) (offsetof(struct cache_entry,name) + (len) + 1)
> +#define directory_entry_size(len) (offsetof(struct directory_entry,pathname) + (len) + 1)
> +#define conflict_entry_size(len) (offsetof(struct conflict_entry,name) + (len) + 1)

These are used by read-cache-v5.c only so far. I'd say move them to read-cache.h or read-cache-v5.c together with the new structs.

Show 19 quoted lines
> +struct ondisk_cache_entry {
> +       unsigned short flags;
> +       unsigned short mode;
> +       struct cache_time mtime;
> +       unsigned int size;
> +       int stat_crc;
> +       unsigned char sha1[20];
> +};
> +
> +struct ondisk_directory_entry {
> +       unsigned int foffset;
> +       unsigned int cr;
> +       unsigned int ncr;
> +       unsigned int nsubtrees;
> +       unsigned int nfiles;
> +       unsigned int nentries;
> +       unsigned char sha1[20];
> +       unsigned short flags;
> +};
Perhaps use uint32_t, uint16_t and friends for all on-disk structures?
Show 56 quoted lines
> +static struct directory_entry *read_directories(unsigned int *dir_offset,
> +                               unsigned int *dir_table_offset,
> +                               void *mmap,
> +                               int mmap_size)
> +{
> +       int i, ondisk_directory_size;
> +       uint32_t *filecrc, *beginning, *end;
> +       struct directory_entry *current = NULL;
> +       struct ondisk_directory_entry *disk_de;
> +       struct directory_entry *de;
> +       unsigned int data_len, len;
> +       char *name;
> +
> +       /*
> +        * Length of pathname + nul byte for termination + size of
> +        * members of ondisk_directory_entry. (Just using the size
> +        * of the struct doesn't work, because there may be padding
> +        * bytes for the struct)
> +        */
> +       ondisk_directory_size = sizeof(disk_de->flags)
> +               + sizeof(disk_de->foffset)
> +               + sizeof(disk_de->cr)
> +               + sizeof(disk_de->ncr)
> +               + sizeof(disk_de->nsubtrees)
> +               + sizeof(disk_de->nfiles)
> +               + sizeof(disk_de->nentries)
> +               + sizeof(disk_de->sha1);
> +       name = ptr_add(mmap, *dir_offset);
> +       beginning = ptr_add(mmap, *dir_table_offset);
> +       end = ptr_add(mmap, *dir_table_offset + 4);
> +       len = ntoh_l(*end) - ntoh_l(*beginning) - ondisk_directory_size - 5;
> +       disk_de = ptr_add(mmap, *dir_offset + len + 1);
> +       de = directory_entry_from_ondisk(disk_de, name, len);
> +       de->next = NULL;
> +
> +       data_len = len + 1 + ondisk_directory_size;
> +       filecrc = ptr_add(mmap, *dir_offset + data_len);
> +       if (!check_crc32(0, ptr_add(mmap, *dir_offset), data_len, ntoh_l(*filecrc)))
> +               goto unmap;
> +
> +       *dir_table_offset += 4;
> +       *dir_offset += data_len + 4; /* crc code */
> +
> +       current = de;
> +       for (i = 0; i < de->de_nsubtrees; i++) {
> +               current->next = read_directories(dir_offset, dir_table_offset,
> +                                               mmap, mmap_size);
> +               while (current->next)
> +                       current = current->next;
> +       }
> +
> +       return de;
> +unmap:
> +       munmap(mmap, mmap_size);
> +       die("directory crc doesn't match for '%s'", de->pathname);
> +}

You don't have to munmap when you die() anway. I'm not sure if flatten the directory hierarchy into a list (linked by next pointer) is a good idea, or we should maintain the tree structure in memory. Still a lot of reading to figure that out..

I skipped from here..
> +static void ce_queue_push(struct cache_entry **head,
> +                            struct cache_entry **tail,
> +                            struct cache_entry *ce)
> +{
...
> +static int read_conflicts(struct conflict_entry **head,
> +                         struct directory_entry *de,
> +                         void **mmap, unsigned long mmap_size)
> +{
till the end of this function. Not interested in conflict stuff yet.
Show 6 quoted lines
> +static struct directory_entry *read_head_directories(struct index_state *istate,
> +                                                    unsigned int *entry_offset,
> +                                                    unsigned int *foffsetblock,
> +                                                    unsigned int *ndirs,
> +                                                    void *mmap, unsigned long mmap_size)
> +{
Maybe read_all_directories is a better nam.
Show 28 quoted lines
> +static int read_index_filtered_v5(struct index_state *istate, void *mmap,
> +                                 unsigned long mmap_size, struct filter_opts *opts)
> +{
> +       unsigned int entry_offset, ndirs, foffsetblock, nr = 0;
> +       struct directory_entry *root_directory, *de;
> +       const char **adjusted_pathspec = NULL;
> +       int need_root = 0, i, n;
> +       char *oldpath, *seen;
> +
> +       ...
> +
> +       de = root_directory;
> +       while (de) {
> +               if (need_root ||
> +                   match_pathspec(adjusted_pathspec, de->pathname, de->de_pathlen, 0, NULL)) {
> +                       unsigned int subdir_foffsetblock = de->de_foffset + foffsetblock;
> +                       unsigned int *off = mmap + subdir_foffsetblock;
> +                       unsigned int subdir_entry_offset = entry_offset + ntoh_l(*off);
> +                       oldpath = de->pathname;
> +                       do {
> +                               if (read_entries(istate, &de, &subdir_entry_offset,
> +                                                &mmap, mmap_size, &nr,
> +                                                &subdir_foffsetblock) < 0)
> +                                       return -1;
> +                       } while (de && !prefixcmp(de->pathname, oldpath));
> +               } else
> +                       de = de->next;
> +       }

Hm.. if we maintain a tree structure here (one link to the first subdir, one link to the next sibling), I think the "do" loop could be done without prefixcmp. Just check if "de" returned by read_entries is the next sibling "de" (iow the end of current directory recursively).

Show 24 quoted lines
> +       istate->cache_nr = nr;
> +       return 0;
> +}
> +
> +static int read_index_v5(struct index_state *istate, void *mmap,
> +                        unsigned long mmap_size, struct filter_opts *opts)
> +{
> +       unsigned int entry_offset, ndirs, foffsetblock, nr = 0;
> +       struct directory_entry *root_directory, *de;
> +
> +       if (opts != NULL)
> +               return read_index_filtered_v5(istate, mmap, mmap_size, opts);
> +
> +       root_directory = read_head_directories(istate, &entry_offset,
> +                                              &foffsetblock, &ndirs,
> +                                              mmap, mmap_size);
> +       de = root_directory;
> +       while (de)
> +               if (read_entries(istate, &de, &entry_offset, &mmap,
> +                                mmap_size, &nr, &foffsetblock) < 0)
> +                       return -1;
> +       istate->cache_nr = nr;
> +       return 0;
> +}

Make it call read_index_filtered_v5 with an empty pathspec instead. match_pathspec* returns true immediately if pathspec is empty. Without the removal of prefixcmp() in the "do" loop mentioned above, read_index_filtered_v5 can't be more expensive than this version.

That was it! Lunch time! Maybe I'll read the rest in the afternoon, or someday next week. -- Duy

Previous: Thomas GummererNext: Thomas Gummerer
Message 27 of 51 in “Index-v5”
  1. 00/19 Index-v5Thomas Gummerer, Jul 12, 2013
  2. 01/19 t2104: Don't fail for index versions other than [23]Thomas Gummerer, Jul 12, 2013
  3. 02/19 read-cache: split index file version specific functionalityThomas Gummerer, Jul 12, 2013
  4. 03/19 read-cache: move index v2 specific functions to their own fileThomas Gummerer, Jul 12, 2013
  5. Duy NguyenJul 14, 2013
  6. Thomas GummererJul 19, 2013
  7. 04/19 read-cache: Re-read index if index file changedThomas Gummerer, Jul 12, 2013
  8. 05/19 Add documentation for the index apiThomas Gummerer, Jul 12, 2013
  9. 06/19 read-cache: add index reading apiThomas Gummerer, Jul 12, 2013
  10. Duy NguyenJul 14, 2013
  11. 07/19 make sure partially read index is not changedThomas Gummerer, Jul 12, 2013
  12. Duy NguyenJul 14, 2013
  13. Thomas GummererJul 17, 2013
  14. 08/19 grep.c: Use index apiThomas Gummerer, Jul 12, 2013
  15. Duy NguyenJul 14, 2013
  16. Thomas GummererJul 15, 2013
  17. 09/19 ls-files.c: use index apiThomas Gummerer, Jul 12, 2013
  18. Duy NguyenJul 14, 2013
  19. Thomas GummererJul 17, 2013
  20. 10/19 documentation: add documentation of the index-v5 file formatThomas Gummerer, Jul 12, 2013
  21. Duy NguyenJul 14, 2013
  22. Thomas GummererJul 17, 2013
  23. Duy NguyenAug 4, 2013
  24. Thomas GummererAug 4, 2013
  25. 11/19 read-cache: make in-memory format aware of stat_crcThomas Gummerer, Jul 12, 2013
  26. 12/19 read-cache: read index-v5Thomas Gummerer, Jul 12, 2013
  27. Duy NguyenJul 14, 2013
  28. Thomas GummererAug 7, 2013
  29. Duy NguyenJul 15, 2013
  30. Thomas GummererJul 17, 2013
  31. Duy NguyenAug 8, 2013
  32. Thomas GummererAug 8, 2013
  33. Thomas GummererAug 9, 2013
  34. Thomas GummererAug 7, 2013
  35. Duy NguyenAug 8, 2013
  36. 13/19 read-cache: read resolve-undo dataThomas Gummerer, Jul 12, 2013
  37. 14/19 read-cache: read cache-tree in index-v5Thomas Gummerer, Jul 12, 2013
  38. 15/19 read-cache: write index-v5Thomas Gummerer, Jul 12, 2013
  39. 16/19 read-cache: write index-v5 cache-tree dataThomas Gummerer, Jul 12, 2013
  40. 17/19 read-cache: write resolve-undo data for index-v5Thomas Gummerer, Jul 12, 2013
  41. 18/19 update-index.c: rewrite index when index-version is givenThomas Gummerer, Jul 12, 2013
  42. 19/19 p0003-index.sh: add perf test for the index formatsThomas Gummerer, Jul 12, 2013
  43. Duy NguyenJul 14, 2013
  44. Thomas GummererJul 15, 2013
  45. Duy NguyenJul 15, 2013
  46. Thomas GummererJul 17, 2013
  47. Junio C HamanoJul 17, 2013
  48. Thomas GummererJul 19, 2013
  49. Junio C HamanoJul 19, 2013
  50. Ramsay JonesJul 16, 2013
  51. Thomas GummererJul 17, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.