Re: [PATCH v2 12/19] read-cache: read index-v5
Duy Nguyen writes:
> On Wed, Jul 17, 2013 at 3:11 PM, Thomas Gummerer wrote:
>> Duy Nguyen writes:
>>
>> [..]
>>
+static int read_entries(struct index_state *istate, struct
directory_entry **de,
+ unsigned int *entry_offset, void **mmap,
+ unsigned long mmap_size, unsigned int *nr,
+ unsigned int *foffsetblock)
+{
+ struct cache_entry *head = NULL, *tail = NULL;
+ struct conflict_entry *conflict_queue;
+ struct cache_entry *ce;
+ int i;
+
+ conflict_queue = NULL;
+ if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
+ return -1;
+ for (i = 0; i < (*de)->de_nfiles; i++) {
+ if (read_entry(&ce,
+ *de,
+ entry_offset,
+ mmap,
+ mmap_size,
+ foffsetblock) < 0)
+ return -1;
+ ce_queue_push(&head, &tail, ce);
+ *foffsetblock += 4;
+
+ /*
+* Add the conflicted entries at the end of the index file
+* to the in memory format
+*/
+ if (conflict_queue &&
+ (conflict_queue->entries->flags & CONFLICT_CONFLICTED)
!= 0 &&
+ !cache_name_compare(conflict_queue->name,
conflict_queue->namelen,
+ ce->name, ce_namelen(ce))) {
+ struct conflict_part *cp;
+ cp = conflict_queue->entries;
+ cp = cp->next;
+ while (cp) {
+ ce = convert_conflict_part(cp,
+ conflict_queue->name,
+ conflict_queue->namelen);
+ ce_queue_push(&head, &tail, ce);
+ conflict_part_head_remove(&cp);
+ }
+ conflict_entry_head_remove(&conflict_queue);
+ }
>>>
>>> I start to wonder if separating staged entries is a good idea. It
>>> seems to make the code more complicated. The good point about conflict
>>> section at the end of the file is you can just truncate() it out.
>>> Another way is putting staged entries in fileentries, sorted
>>> alphabetically then by stage number, and a flag indicating if the
>>> entry is valid. When you remove resolve an entry, just set the flag to
>>> invalid (partial write), so that read code will skip it.
>>>
>>> I think this approach is reasonably cheap (unless there are a lot of
>>> conflicts) and it simplifies this piece of code. truncate() may be
>>> overrated anyway. In my experience, I "git add " as soon as I
>>> resolve (so that "git diff" shrinks). One entry at a time, one
>>> index write at a time. I don't think I ever resolve everything then
>>> "git add -u .", which is where truncate() shines because staged
>>> entries are removed all at once. We should optimize for one file
>>> resolution at a time, imo.
>>
>> Thanks for your comments. I'll address the other ones once we decided
>> to do with the conflicts.
>>
>> It does make the code quite a bit more complicated, but also has one
>> advantage that you overlooked.
>
> I did overlook, although my goal is to keep the code simpler, not more
> comlicated. The thinking is if we can find everything in fileentries
> table, the code here is simplified, so..
>
>> We wouldn't truncate() when resolving
>> the conflicts. The resolve undo data is stored with the conflicts and
>> therefore we could just flip a bit and set the stage of the cache-entry
>> in the main index to 0 (always once we got partial writing). This can
>> be fast both in case we resolve one entry at a time and when we resolve
>> a lot of entries. The advantage is even bigger when we resolve one
>> entry at a time, when we otherwise would have to re-write the index for
>> each conflict resolution.
>
> If I understand it correctly, filentries can only contain stage-0 or
> stage-1 entries, "stage > 0" entries are stored in conflict data. Once
> a conflict is solved, you update the stage-1 entry in fileentries,
> turning it to stage-0 and recalculate the entry checksum. Conflict
> data remains there to function as the old REUC extension. Correct?
>
> First of all, if that's true, we only need 1 bit for stage in fileentries
> table.
>
> Secondly, you may get away with looking up to conflict data in this
> function by storing all stages in fileentries (now we need 2-bit
> stage), replicated in conflict data for reuc function. When you
> resolve conflict, you flip stage-1
Re: [PATCH v2 12/19] read-cache: read index-v5
Duy Nguyen writes:
> On Wed, Jul 17, 2013 at 3:11 PM, Thomas Gummerer wrote:
>> Duy Nguyen writes:
>>
>> [..]
>>
+static int read_entries(struct index_state *istate, struct
directory_entry **de,
+ unsigned int *entry_offset, void **mmap,
+ unsigned long mmap_size, unsigned int *nr,
+ unsigned int *foffsetblock)
+{
+ struct cache_entry *head = NULL, *tail = NULL;
+ struct conflict_entry *conflict_queue;
+ struct cache_entry *ce;
+ int i;
+
+ conflict_queue = NULL;
+ if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
+ return -1;
+ for (i = 0; i < (*de)->de_nfiles; i++) {
+ if (read_entry(&ce,
+ *de,
+ entry_offset,
+ mmap,
+ mmap_size,
+ foffsetblock) < 0)
+ return -1;
+ ce_queue_push(&head, &tail, ce);
+ *foffsetblock += 4;
+
+ /*
+* Add the conflicted entries at the end of the index file
+* to the in memory format
+*/
+ if (conflict_queue &&
+ (conflict_queue->entries->flags & CONFLICT_CONFLICTED)
!= 0 &&
+ !cache_name_compare(conflict_queue->name,
conflict_queue->namelen,
+ ce->name, ce_namelen(ce))) {
+ struct conflict_part *cp;
+ cp = conflict_queue->entries;
+ cp = cp->next;
+ while (cp) {
+ ce = convert_conflict_part(cp,
+ conflict_queue->name,
+ conflict_queue->namelen);
+ ce_queue_push(&head, &tail, ce);
+ conflict_part_head_remove(&cp);
+ }
+ conflict_entry_head_remove(&conflict_queue);
+ }
>>>
>>> I start to wonder if separating staged entries is a good idea. It
>>> seems to make the code more complicated. The good point about conflict
>>> section at the end of the file is you can just truncate() it out.
>>> Another way is putting staged entries in fileentries, sorted
>>> alphabetically then by stage number, and a flag indicating if the
>>> entry is valid. When you remove resolve an entry, just set the flag to
>>> invalid (partial write), so that read code will skip it.
>>>
>>> I think this approach is reasonably cheap (unless there are a lot of
>>> conflicts) and it simplifies this piece of code. truncate() may be
>>> overrated anyway. In my experience, I "git add " as soon as I
>>> resolve (so that "git diff" shrinks). One entry at a time, one
>>> index write at a time. I don't think I ever resolve everything then
>>> "git add -u .", which is where truncate() shines because staged
>>> entries are removed all at once. We should optimize for one file
>>> resolution at a time, imo.
>>
>> Thanks for your comments. I'll address the other ones once we decided
>> to do with the conflicts.
>>
>> It does make the code quite a bit more complicated, but also has one
>> advantage that you overlooked.
>
> I did overlook, although my goal is to keep the code simpler, not more
> comlicated. The thinking is if we can find everything in fileentries
> table, the code here is simplified, so..
>
>> We wouldn't truncate() when resolving
>> the conflicts. The resolve undo data is stored with the conflicts and
>> therefore we could just flip a bit and set the stage of the cache-entry
>> in the main index to 0 (always once we got partial writing). This can
>> be fast both in case we resolve one entry at a time and when we resolve
>> a lot of entries. The advantage is even bigger when we resolve one
>> entry at a time, when we otherwise would have to re-write the index for
>> each conflict resolution.
>
> If I understand it correctly, filentries can only contain stage-0 or
> stage-1 entries, "stage > 0" entries are stored in conflict data. Once
> a conflict is solved, you update the stage-1 entry in fileentries,
> turning it to stage-0 and recalculate the entry checksum. Conflict
> data remains there to function as the old REUC extension. Correct?
Correct.
> First of all, if that's true, we only need 1 bit for stage in fileentries
> table.
>
> Secondly, you may get away with looking up to conflict data in this
> function by storing all stages in fileentries (now we need 2-bit
> stage), replicated in conflict data for reuc function. When you
> resolve conflict, you flip
Re: [PATCH v2 12/19] read-cache: read index-v5
On Wed, Aug 7, 2013 at 3:23 PM, Thomas Gummerer wrote:
>> On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer
>> wrote:
>>> +static void ce_queue_push(struct cache_entry **head,
>>> +struct cache_entry **tail,
>>> +struct cache_entry *ce)
>>> +{
>>> + if (!*head) {
>>> + *head = *tail = ce;
>>> + (*tail)->next = NULL;
>>> + return;
>>> + }
>>> +
>>> + (*tail)->next = ce;
>>> + ce->next = NULL;
>>> + *tail = (*tail)->next;
>>
>> No no no. "next" is for name-hash.c don't "reuse" it here. And I don't
>> think you really need to maintain a linked list of cache_entries by
>> the way. More on read_entries comments below..
>
> You're right, I don't need it for the reading code. I do need to keep a
> list of cache-entries for writing though, where a linked list is best
> suited for the task. I'll use a next_ce pointer for that.
Hmm.. yeah you need to maintain temporary structures before writing
out direntries, then fileentries table. We can't just write as we
traverse through the cache in one go. Maybe a new field in cache_entry
for the linked list, or maintain the linked list off cache_entry..
whichever is easier for you.
> I've tried implementing both versions with the internal tree structure,
> see below for timings.
>
> simpleapi is the code that was posted to the list, HEAD uses a
> tree-structure for the directories internally, and replaces strcmp with
> cache_name_compare and leaves out the prefix. This tree uses dummy
> entries for the sub-directories.
>
> Dummy entries are single NUL-bytes mixed with the cache-entries, which
> should give optimal performance. I haven't thought much about
> corruption of the index, but I don't think we would need any additional
> crc checksums or similar.
>
> The performance advantage seems very slim to none when using the dummy
> entries to avoid the comparison though, so I don't think it makes sense
> to make the index more complicated for a very small speed-up.
Agreed.
> Testsimpleapi HEAD
> this tree
> -
> 0003.2: v[23]: update-index 3.22(2.61+0.58) 3.20(2.56+0.61)
> -0.6%3.22(2.67+0.53) +0.0%
> 0003.3: v[23]: grep nonexistent -- subdir 1.65(1.36+0.27) 1.65(1.34+0.30)
> +0.0%1.67(1.34+0.31) +1.2%
> 0003.4: v[23]: ls-files -- subdir 1.50(1.20+0.29) 1.54(1.18+0.34)
> +2.7%1.53(1.22+0.30) +2.0%
> 0003.6: v4: update-index2.69(2.28+0.39) 2.70(2.21+0.47)
> +0.4%2.70(2.27+0.41) +0.4%
> 0003.7: v4: grep nonexistent -- subdir 1.33(0.98+0.34) 1.36(1.01+0.33)
> +2.3%1.34(1.03+0.30) +0.8%
> 0003.8: v4: ls-files -- subdir 1.21(0.86+0.33) 1.23(0.91+0.30)
> +1.7%1.22(0.90+0.30) +0.8%
> 0003.10: v5: update-index 2.12(1.58+0.52) 2.20(1.67+0.52)
> +3.8%2.19(1.66+0.51) +3.3%
> 0003.11: v5: ls-files 1.57(1.21+0.34) 1.55(1.20+0.33)
> -1.3%1.52(1.21+0.29) -3.2%
> 0003.12: v5: grep nonexistent -- subdir 0.08(0.06+0.01) 0.07(0.04+0.02)
> -12.5% 0.07(0.04+0.02) -12.5%
> 0003.13: v5: ls-files -- subdir 0.07(0.04+0.01) 0.06(0.05+0.00)
> -14.3% 0.07(0.05+0.01) +0.0%
--
Duy
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2 12/19] read-cache: read index-v5
On Wed, Jul 17, 2013 at 3:11 PM, Thomas Gummerer wrote:
> Duy Nguyen writes:
>
> [..]
>
>>> +static int read_entries(struct index_state *istate, struct directory_entry
>>> **de,
>>> + unsigned int *entry_offset, void **mmap,
>>> + unsigned long mmap_size, unsigned int *nr,
>>> + unsigned int *foffsetblock)
>>> +{
>>> + struct cache_entry *head = NULL, *tail = NULL;
>>> + struct conflict_entry *conflict_queue;
>>> + struct cache_entry *ce;
>>> + int i;
>>> +
>>> + conflict_queue = NULL;
>>> + if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
>>> + return -1;
>>> + for (i = 0; i < (*de)->de_nfiles; i++) {
>>> + if (read_entry(&ce,
>>> + *de,
>>> + entry_offset,
>>> + mmap,
>>> + mmap_size,
>>> + foffsetblock) < 0)
>>> + return -1;
>>> + ce_queue_push(&head, &tail, ce);
>>> + *foffsetblock += 4;
>>> +
>>> + /*
>>> +* Add the conflicted entries at the end of the index file
>>> +* to the in memory format
>>> +*/
>>> + if (conflict_queue &&
>>> + (conflict_queue->entries->flags & CONFLICT_CONFLICTED)
>>> != 0 &&
>>> + !cache_name_compare(conflict_queue->name,
>>> conflict_queue->namelen,
>>> + ce->name, ce_namelen(ce))) {
>>> + struct conflict_part *cp;
>>> + cp = conflict_queue->entries;
>>> + cp = cp->next;
>>> + while (cp) {
>>> + ce = convert_conflict_part(cp,
>>> + conflict_queue->name,
>>> + conflict_queue->namelen);
>>> + ce_queue_push(&head, &tail, ce);
>>> + conflict_part_head_remove(&cp);
>>> + }
>>> + conflict_entry_head_remove(&conflict_queue);
>>> + }
>>
>> I start to wonder if separating staged entries is a good idea. It
>> seems to make the code more complicated. The good point about conflict
>> section at the end of the file is you can just truncate() it out.
>> Another way is putting staged entries in fileentries, sorted
>> alphabetically then by stage number, and a flag indicating if the
>> entry is valid. When you remove resolve an entry, just set the flag to
>> invalid (partial write), so that read code will skip it.
>>
>> I think this approach is reasonably cheap (unless there are a lot of
>> conflicts) and it simplifies this piece of code. truncate() may be
>> overrated anyway. In my experience, I "git add " as soon as I
>> resolve (so that "git diff" shrinks). One entry at a time, one
>> index write at a time. I don't think I ever resolve everything then
>> "git add -u .", which is where truncate() shines because staged
>> entries are removed all at once. We should optimize for one file
>> resolution at a time, imo.
>
> Thanks for your comments. I'll address the other ones once we decided
> to do with the conflicts.
>
> It does make the code quite a bit more complicated, but also has one
> advantage that you overlooked.
I did overlook, although my goal is to keep the code simpler, not more
comlicated. The thinking is if we can find everything in fileentries
table, the code here is simplified, so..
> We wouldn't truncate() when resolving
> the conflicts. The resolve undo data is stored with the conflicts and
> therefore we could just flip a bit and set the stage of the cache-entry
> in the main index to 0 (always once we got partial writing). This can
> be fast both in case we resolve one entry at a time and when we resolve
> a lot of entries. The advantage is even bigger when we resolve one
> entry at a time, when we otherwise would have to re-write the index for
> each conflict resolution.
If I understand it correctly, filentries can only contain stage-0 or
stage-1 entries, "stage > 0" entries are stored in conflict data. Once
a conflict is solved, you update the stage-1 entry in fileentries,
turning it to stage-0 and recalculate the entry checksum. Conflict
data remains there to function as the old REUC extension. Correct?
First of all, if that's true, we only need 1 bit for stage in fileentries table.
Secondly, you may get away with looking up to conflict data in this
function by storing all stages in fileentries (now we need 2-bit
stage), replicated in conflict data for reuc function. When you
resolve conflict, you flip stage-1 to stage-0, and flip (a new bit) to
mark stage-2 entry invalid so the code knows to skip it. Next time the
index is rewritten, invalid entr
Re: [PATCH v2 12/19] read-cache: read index-v5
Duy Nguyen writes:
> A little bit more..
>
> On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer
> wrote:
>> +static void ce_queue_push(struct cache_entry **head,
>> +struct cache_entry **tail,
>> +struct cache_entry *ce)
>> +{
>> + if (!*head) {
>> + *head = *tail = ce;
>> + (*tail)->next = NULL;
>> + return;
>> + }
>> +
>> + (*tail)->next = ce;
>> + ce->next = NULL;
>> + *tail = (*tail)->next;
>
> No no no. "next" is for name-hash.c don't "reuse" it here. And I don't
> think you really need to maintain a linked list of cache_entries by
> the way. More on read_entries comments below..
You're right, I don't need it for the reading code. I do need to keep a
list of cache-entries for writing though, where a linked list is best
suited for the task. I'll use a next_ce pointer for that.
>> +}
>> +
>> +static struct cache_entry *ce_queue_pop(struct cache_entry **head)
>> +{
>> + struct cache_entry *ce;
>> +
>> + ce = *head;
>> + *head = (*head)->next;
>> + return ce;
>> +}
>
> Same as ce_queue_push.
>
>> +static int read_entries(struct index_state *istate, struct directory_entry
>> **de,
>> + unsigned int *entry_offset, void **mmap,
>> + unsigned long mmap_size, unsigned int *nr,
>> + unsigned int *foffsetblock)
>> +{
>> + struct cache_entry *head = NULL, *tail = NULL;
>> + struct conflict_entry *conflict_queue;
>> + struct cache_entry *ce;
>> + int i;
>> +
>> + conflict_queue = NULL;
>> + if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
>> + return -1;
>> + for (i = 0; i < (*de)->de_nfiles; i++) {
>> + if (read_entry(&ce,
>> + *de,
>> + entry_offset,
>> + mmap,
>> + mmap_size,
>> + foffsetblock) < 0)
>> + return -1;
>> + ce_queue_push(&head, &tail, ce);
>> + *foffsetblock += 4;
>> +
>> + /*
>> +* Add the conflicted entries at the end of the index file
>> +* to the in memory format
>> +*/
>> + if (conflict_queue &&
>> + (conflict_queue->entries->flags & CONFLICT_CONFLICTED)
>> != 0 &&
>> + !cache_name_compare(conflict_queue->name,
>> conflict_queue->namelen,
>> + ce->name, ce_namelen(ce))) {
>> + struct conflict_part *cp;
>> + cp = conflict_queue->entries;
>> + cp = cp->next;
>> + while (cp) {
>> + ce = convert_conflict_part(cp,
>> + conflict_queue->name,
>> + conflict_queue->namelen);
>> + ce_queue_push(&head, &tail, ce);
>> + conflict_part_head_remove(&cp);
>> + }
>> + conflict_entry_head_remove(&conflict_queue);
>> + }
>
> I start to wonder if separating staged entries is a good idea. It
> seems to make the code more complicated. The good point about conflict
> section at the end of the file is you can just truncate() it out.
> Another way is putting staged entries in fileentries, sorted
> alphabetically then by stage number, and a flag indicating if the
> entry is valid. When you remove resolve an entry, just set the flag to
> invalid (partial write), so that read code will skip it.
>
> I think this approach is reasonably cheap (unless there are a lot of
> conflicts) and it simplifies this piece of code. truncate() may be
> overrated anyway. In my experience, I "git add " as soon as I
> resolve (so that "git diff" shrinks). One entry at a time, one
> index write at a time. I don't think I ever resolve everything then
> "git add -u .", which is where truncate() shines because staged
> entries are removed all at once. We should optimize for one file
> resolution at a time, imo.
>
>> + }
>> +
>> + *de = (*de)->next;
>> +
>> + while (head) {
>> + if (*de != NULL
>> + && strcmp(head->name, (*de)->pathname) > 0) {
>> + read_entries(istate,
>> +de,
>> +entry_offset,
>> +mmap,
>> +mmap_size,
>> +nr,
>> +foffsetblock);
>> + } else {
>> + ce = ce_queue_pop(&head);
>> + set_index_entry(istate, *nr, ce);
>> +
Re: [PATCH v2 12/19] read-cache: read index-v5
Duy Nguyen writes:
> On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer
> wrote:
>> +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
Makes sense, thanks.
>> #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.
Thanks.
>> +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?
We got this in the makefile, so I think we should be fine without it.
It still makes sense for clarity though I think.
ifdef NO_UINTMAX_T
BASIC_CFLAGS += -Duintmax_t=uint32_t
endif
While at it I'll make the code for v[234] use them too.
>> +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)
>> +
Re: [PATCH v2 12/19] read-cache: read index-v5
Duy Nguyen writes:
[..]
>> +static int read_entries(struct index_state *istate, struct directory_entry
>> **de,
>> + unsigned int *entry_offset, void **mmap,
>> + unsigned long mmap_size, unsigned int *nr,
>> + unsigned int *foffsetblock)
>> +{
>> + struct cache_entry *head = NULL, *tail = NULL;
>> + struct conflict_entry *conflict_queue;
>> + struct cache_entry *ce;
>> + int i;
>> +
>> + conflict_queue = NULL;
>> + if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
>> + return -1;
>> + for (i = 0; i < (*de)->de_nfiles; i++) {
>> + if (read_entry(&ce,
>> + *de,
>> + entry_offset,
>> + mmap,
>> + mmap_size,
>> + foffsetblock) < 0)
>> + return -1;
>> + ce_queue_push(&head, &tail, ce);
>> + *foffsetblock += 4;
>> +
>> + /*
>> +* Add the conflicted entries at the end of the index file
>> +* to the in memory format
>> +*/
>> + if (conflict_queue &&
>> + (conflict_queue->entries->flags & CONFLICT_CONFLICTED)
>> != 0 &&
>> + !cache_name_compare(conflict_queue->name,
>> conflict_queue->namelen,
>> + ce->name, ce_namelen(ce))) {
>> + struct conflict_part *cp;
>> + cp = conflict_queue->entries;
>> + cp = cp->next;
>> + while (cp) {
>> + ce = convert_conflict_part(cp,
>> + conflict_queue->name,
>> + conflict_queue->namelen);
>> + ce_queue_push(&head, &tail, ce);
>> + conflict_part_head_remove(&cp);
>> + }
>> + conflict_entry_head_remove(&conflict_queue);
>> + }
>
> I start to wonder if separating staged entries is a good idea. It
> seems to make the code more complicated. The good point about conflict
> section at the end of the file is you can just truncate() it out.
> Another way is putting staged entries in fileentries, sorted
> alphabetically then by stage number, and a flag indicating if the
> entry is valid. When you remove resolve an entry, just set the flag to
> invalid (partial write), so that read code will skip it.
>
> I think this approach is reasonably cheap (unless there are a lot of
> conflicts) and it simplifies this piece of code. truncate() may be
> overrated anyway. In my experience, I "git add " as soon as I
> resolve (so that "git diff" shrinks). One entry at a time, one
> index write at a time. I don't think I ever resolve everything then
> "git add -u .", which is where truncate() shines because staged
> entries are removed all at once. We should optimize for one file
> resolution at a time, imo.
Thanks for your comments. I'll address the other ones once we decided
to do with the conflicts.
It does make the code quite a bit more complicated, but also has one
advantage that you overlooked. We wouldn't truncate() when resolving
the conflicts. The resolve undo data is stored with the conflicts and
therefore we could just flip a bit and set the stage of the cache-entry
in the main index to 0 (always once we got partial writing). This can
be fast both in case we resolve one entry at a time and when we resolve
a lot of entries. The advantage is even bigger when we resolve one
entry at a time, when we otherwise would have to re-write the index for
each conflict resolution.
[..]
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2 12/19] read-cache: read index-v5
A little bit more..
On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer wrote:
> +static void ce_queue_push(struct cache_entry **head,
> +struct cache_entry **tail,
> +struct cache_entry *ce)
> +{
> + if (!*head) {
> + *head = *tail = ce;
> + (*tail)->next = NULL;
> + return;
> + }
> +
> + (*tail)->next = ce;
> + ce->next = NULL;
> + *tail = (*tail)->next;
No no no. "next" is for name-hash.c don't "reuse" it here. And I don't
think you really need to maintain a linked list of cache_entries by
the way. More on read_entries comments below..
> +}
> +
> +static struct cache_entry *ce_queue_pop(struct cache_entry **head)
> +{
> + struct cache_entry *ce;
> +
> + ce = *head;
> + *head = (*head)->next;
> + return ce;
> +}
Same as ce_queue_push.
> +static int read_entries(struct index_state *istate, struct directory_entry
> **de,
> + unsigned int *entry_offset, void **mmap,
> + unsigned long mmap_size, unsigned int *nr,
> + unsigned int *foffsetblock)
> +{
> + struct cache_entry *head = NULL, *tail = NULL;
> + struct conflict_entry *conflict_queue;
> + struct cache_entry *ce;
> + int i;
> +
> + conflict_queue = NULL;
> + if (read_conflicts(&conflict_queue, *de, mmap, mmap_size) < 0)
> + return -1;
> + for (i = 0; i < (*de)->de_nfiles; i++) {
> + if (read_entry(&ce,
> + *de,
> + entry_offset,
> + mmap,
> + mmap_size,
> + foffsetblock) < 0)
> + return -1;
> + ce_queue_push(&head, &tail, ce);
> + *foffsetblock += 4;
> +
> + /*
> +* Add the conflicted entries at the end of the index file
> +* to the in memory format
> +*/
> + if (conflict_queue &&
> + (conflict_queue->entries->flags & CONFLICT_CONFLICTED) !=
> 0 &&
> + !cache_name_compare(conflict_queue->name,
> conflict_queue->namelen,
> + ce->name, ce_namelen(ce))) {
> + struct conflict_part *cp;
> + cp = conflict_queue->entries;
> + cp = cp->next;
> + while (cp) {
> + ce = convert_conflict_part(cp,
> + conflict_queue->name,
> + conflict_queue->namelen);
> + ce_queue_push(&head, &tail, ce);
> + conflict_part_head_remove(&cp);
> + }
> + conflict_entry_head_remove(&conflict_queue);
> + }
I start to wonder if separating staged entries is a good idea. It
seems to make the code more complicated. The good point about conflict
section at the end of the file is you can just truncate() it out.
Another way is putting staged entries in fileentries, sorted
alphabetically then by stage number, and a flag indicating if the
entry is valid. When you remove resolve an entry, just set the flag to
invalid (partial write), so that read code will skip it.
I think this approach is reasonably cheap (unless there are a lot of
conflicts) and it simplifies this piece of code. truncate() may be
overrated anyway. In my experience, I "git add " as soon as I
resolve (so that "git diff" shrinks). One entry at a time, one
index write at a time. I don't think I ever resolve everything then
"git add -u .", which is where truncate() shines because staged
entries are removed all at once. We should optimize for one file
resolution at a time, imo.
> + }
> +
> + *de = (*de)->next;
> +
> + while (head) {
> + if (*de != NULL
> + && strcmp(head->name, (*de)->pathname) > 0) {
> + read_entries(istate,
> +de,
> +entry_offset,
> +mmap,
> +mmap_size,
> +nr,
> +foffsetblock);
> + } else {
> + ce = ce_queue_pop(&head);
> + set_index_entry(istate, *nr, ce);
> + (*nr)++;
> + ce->next = NULL;
> + }
In this loop, you do some sort of merge sort combining a list of
sorted files and a list of sorted directories (which will be expanded
to bunches of files by the recursive read_entries). strcmp() does two
things. Assume we're in directory 'a', it makes sure that subdirector
Re: [PATCH v2 12/19] read-cache: read index-v5
On Sat, Jul 13, 2013 at 12:26 AM, Thomas Gummerer wrote:
> +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.
> +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?
> +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 voi
