[PATCH 01/14] Extend index to save more flags

[PATCH 01/14] Extend index to save more flags

[Nguyễn Thái Ngọc Duy]

The on-disk format of index only saves 16 bit flags, nearly all have
been used. The last bit (CE_EXTENDED) is used to for future extension.

This patch extends index entry format to save more flags in future.
The new entry format will be used when CE_EXTENDED bit is 1.

Because older implementation may not understand CE_EXTENDED bit and
misread the new format, if there is any extended entry in index, index
header version will turn 3, which makes it incompatible for older git.
If there is none, header version will return to 2 again.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h      |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 read-cache.c |   51 +++++++++++++++++++++++++++++++++++++++++----------
 2 files changed, 95 insertions(+), 14 deletions(-)

diff --git a/cache.h b/cache.h
index f4b8ddf..77b6eb3 100644
--- a/cache.h
+++ b/cache.h
@@ -109,6 +109,26 @@ struct ondisk_cache_entry {
 	char name[FLEX_ARRAY]; /* more */
 };
 
+/*
+ * This struct is used when CE_EXTENDED bit is 1
+ * The struct must match ondisk_cache_entry exactly from
+ * ctime till flags
+ */
+struct ondisk_cache_entry_extended {
+	struct cache_time ctime;
+	struct cache_time mtime;
+	unsigned int dev;
+	unsigned int ino;
+	unsigned int mode;
+	unsigned int uid;
+	unsigned int gid;
+	unsigned int size;
+	unsigned char sha1[20];
+	unsigned short flags;
+	unsigned short flags2;
+	char name[FLEX_ARRAY]; /* more */
+};
+
 struct cache_entry {
 	unsigned int ce_ctime;
 	unsigned int ce_mtime;
@@ -130,7 +150,15 @@ struct cache_entry {
 #define CE_VALID     (0x8000)
 #define CE_STAGESHIFT 12
 
-/* In-memory only */
+/*
+ * Range 0xFFFF0000 in ce_flags is divided into
+ * two parts: in-memory flags and on-disk ones.
+ * Flags in CE_EXTENDED_FLAGS will get saved on-disk
+ * if you want to save a new flag, add it in
+ * CE_EXTENDED_FLAGS
+ *
+ * In-memory only flags
+ */
 #define CE_UPDATE    (0x10000)
 #define CE_REMOVE    (0x20000)
 #define CE_UPTODATE  (0x40000)
@@ -140,6 +168,24 @@ struct cache_entry {
 #define CE_UNHASHED  (0x200000)
 
 /*
+ * Extended on-disk flags
+ */
+/* CE_EXTENDED2 is for future extension */
+#define CE_EXTENDED2 0x80000000
+
+#define CE_EXTENDED_FLAGS (0)
+
+/*
+ * Safeguard to avoid saving wrong flags:
+ *  - CE_EXTENDED2 won't get saved until its semantic is known
+ *  - Bits in 0x0000FFFF have been saved in ce_flags already
+ *  - Bits in 0x003F0000 are currently in-memory flags
+ */
+#if CE_EXTENDED_FLAGS & 0x80CFFFFF
+#error "CE_EXTENDED_FLAGS out of range"
+#endif
+
+/*
  * Copy the sha1 and stat state of a cache entry from one to
  * another. But we never change the name, or the hash state!
  */
@@ -171,7 +217,9 @@ static inline size_t ce_namelen(const struct cache_entry *ce)
 }
 
 #define ce_size(ce) cache_entry_size(ce_namelen(ce))
-#define ondisk_ce_size(ce) ondisk_cache_entry_size(ce_namelen(ce))
+#define ondisk_ce_size(ce) (((ce)->ce_flags & CE_EXTENDED) ? \
+			    ondisk_cache_entry_extended_size(ce_namelen(ce)) : \
+			    ondisk_cache_entry_size(ce_namelen(ce)))
 #define ce_stage(ce) ((CE_STAGEMASK & (ce)->ce_flags) >> CE_STAGESHIFT)
 #define ce_uptodate(ce) ((ce)->ce_flags & CE_UPTODATE)
 #define ce_mark_uptodate(ce) ((ce)->ce_flags |= CE_UPTODATE)
@@ -214,8 +262,10 @@ static inline int ce_to_dtype(const struct cache_entry *ce)
 	(S_ISREG(mode) ? (S_IFREG | ce_permissions(mode)) : \
 	S_ISLNK(mode) ? S_IFLNK : S_ISDIR(mode) ? S_IFDIR : S_IFGITLINK)
 
-#define cache_entry_size(len) ((offsetof(struct cache_entry,name) + (len) + 8) & ~7)
-#define ondisk_cache_entry_size(len) ((offsetof(struct ondisk_cache_entry,name) + (len) + 8) & ~7)
+#define flexible_size(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)
+#define cache_entry_size(len) flexible_size(cache_entry,len)
+#define ondisk_cache_entry_size(len) flexible_size(ondisk_cache_entry,len)
+#define ondisk_cache_entry_extended_size(len) flexible_size(ondisk_cache_entry_extended,len)
 
 struct index_state {
 	struct cache_entry **cache;
diff --git a/read-cache.c b/read-cache.c
index c5a8659..667c36b 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1096,7 +1096,7 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
 
 	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
 		return error("bad signature");
-	if (hdr->hdr_version != htonl(2))
+	if (hdr->hdr_version != htonl(2) && hdr->hdr_version != htonl(3))
 		return error("bad index version");
 	SHA1_Init(&c);
 	SHA1_Update(&c, hdr, size - 20);
@@ -1131,6 +1131,7 @@ int read_index(struct index_state *istate)
 static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_entry *ce)
 {
 	size_t len;
+	const char *name;
 
 	ce->ce_ctime = ntohl(ondisk->ctime.sec);
 	ce->ce_mtime = ntohl(ondisk->mtime.sec);
@@ -1143,19 +1144,31 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en
 	/* On-disk flags are just 16 bits */
 	ce->ce_flags = ntohs(ondisk->flags);
 
-	/* For future extension: we do not understand this entry yet */
-	if (ce->ce_flags & CE_EXTENDED)
-		die("Unknown index entry format");
 	hashcpy(ce->sha1, ondisk->sha1);
 
 	len = ce->ce_flags & CE_NAMEMASK;
+
+	if (ce->ce_flags & CE_EXTENDED) {
+		struct ondisk_cache_entry_extended *ondisk2;
+		int extended_flags;
+		ondisk2 = (struct ondisk_cache_entry_extended *)ondisk;
+		extended_flags = ntohs(ondisk2->flags2) << 16;
+		/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */
+		if (extended_flags & ~CE_EXTENDED_FLAGS)
+			die("Unknown index entry format %08x", extended_flags);
+		ce->ce_flags |= extended_flags;
+		name = ondisk2->name;
+	}
+	else
+		name = ondisk->name;
+
 	if (len == CE_NAMEMASK)
-		len = strlen(ondisk->name);
+		len = strlen(name);
 	/*
 	 * NEEDSWORK: If the original index is crafted, this copy could
 	 * go unchecked.
 	 */
-	memcpy(ce->name, ondisk->name, len + 1);
+	memcpy(ce->name, name, len + 1);
 }
 
 static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entries)
@@ -1415,6 +1428,7 @@ static int ce_write_entry(SHA_CTX *c, int fd, struct cache_entry *ce)
 {
 	int size = ondisk_ce_size(ce);
 	struct ondisk_cache_entry *ondisk = xcalloc(1, size);
+	char *name;
 
 	ondisk->ctime.sec = htonl(ce->ce_ctime);
 	ondisk->ctime.nsec = 0;
@@ -1428,7 +1442,15 @@ static int ce_write_entry(SHA_CTX *c, int fd, struct cache_entry *ce)
 	ondisk->size = htonl(ce->ce_size);
 	hashcpy(ondisk->sha1, ce->sha1);
 	ondisk->flags = htons(ce->ce_flags);
-	memcpy(ondisk->name, ce->name, ce_namelen(ce));
+	if (ce->ce_flags & CE_EXTENDED) {
+		struct ondisk_cache_entry_extended *ondisk2;
+		ondisk2 = (struct ondisk_cache_entry_extended *)ondisk;
+		ondisk2->flags2 = htons((ce->ce_flags & CE_EXTENDED_FLAGS) >> 16);
+		name = ondisk2->name;
+	}
+	else
+		name = ondisk->name;
+	memcpy(name, ce->name, ce_namelen(ce));
 
 	return ce_write(c, fd, ondisk, size);
 }
@@ -1437,16 +1459,25 @@ int write_index(const struct index_state *istate, int newfd)
 {
 	SHA_CTX c;
 	struct cache_header hdr;
-	int i, err, removed;
+	int i, err, removed, extended;
 	struct cache_entry **cache = istate->cache;
 	int entries = istate->cache_nr;
 
-	for (i = removed = 0; i < entries; i++)
+	for (i = removed = extended = 0; i < entries; i++) {
 		if (cache[i]->ce_flags & CE_REMOVE)
 			removed++;
 
+		/* reduce extended entries if possible */
+		cache[i]->ce_flags &= ~CE_EXTENDED;
+		if (cache[i]->ce_flags & CE_EXTENDED_FLAGS) {
+			extended++;
+			cache[i]->ce_flags |= CE_EXTENDED;
+		}
+	}
+
 	hdr.hdr_signature = htonl(CACHE_SIGNATURE);
-	hdr.hdr_version = htonl(2);
+	/* for extended format, increase version so older git won't try to read it */
+	hdr.hdr_version = htonl(extended ? 3 : 2);
 	hdr.hdr_entries = htonl(entries - removed);
 
 	SHA1_Init(&c);
-- 
1.6.0.96.g2fad1.dirty

Re: [PATCH 01/14] Extend index to save more flags

[Jakub Narebski]

Comments below are just nitpicking. Feel free to diregard them...

Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:

> The on-disk format of index only saves 16 bit flags, nearly all have
> been used. The last bit (CE_EXTENDED) is used to for future extension.
> 
> This patch extends index entry format to save more flags in future.
> The new entry format will be used when CE_EXTENDED bit is 1.
> 
> Because older implementation may not understand CE_EXTENDED bit and
> misread the new format, if there is any extended entry in index, index
> header version will turn 3, which makes it incompatible for older git.
> If there is none, header version will return to 2 again.
> 
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>

It would be nice if at least this part of series got accepted...

> ---
>  cache.h      |   58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----
>  read-cache.c |   51 +++++++++++++++++++++++++++++++++++++++++----------
>  2 files changed, 95 insertions(+), 14 deletions(-)
> 
> diff --git a/cache.h b/cache.h
> index f4b8ddf..77b6eb3 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -109,6 +109,26 @@ struct ondisk_cache_entry {
>  	char name[FLEX_ARRAY]; /* more */
>  };
>  
> +/*
> + * This struct is used when CE_EXTENDED bit is 1
> + * The struct must match ondisk_cache_entry exactly from
> + * ctime till flags
> + */

Errr... "must match"? Wouldn't "does match" be better?
This type is defined below, not is to be defined...

> +struct ondisk_cache_entry_extended {
> +	struct cache_time ctime;
> +	struct cache_time mtime;
> +	unsigned int dev;
> +	unsigned int ino;
> +	unsigned int mode;
> +	unsigned int uid;
> +	unsigned int gid;
> +	unsigned int size;
> +	unsigned char sha1[20];
> +	unsigned short flags;
> +	unsigned short flags2;

flags and flags2? Why not flags1 and flags2, or flags[2], or flags and
flags_ext/flags_extended?

Just nitpicking.

> +	char name[FLEX_ARRAY]; /* more */
> +};
> +
>  struct cache_entry {
>  	unsigned int ce_ctime;
>  	unsigned int ce_mtime;
> @@ -130,7 +150,15 @@ struct cache_entry {
>  #define CE_VALID     (0x8000)
>  #define CE_STAGESHIFT 12
>  
> -/* In-memory only */
> +/*
> + * Range 0xFFFF0000 in ce_flags is divided into
> + * two parts: in-memory flags and on-disk ones.
> + * Flags in CE_EXTENDED_FLAGS will get saved on-disk

Semicolon at the end of below text to separate, I think. Or at least
comma.

> + * if you want to save a new flag, add it in
> + * CE_EXTENDED_FLAGS

Nice comment.

> + *
> + * In-memory only flags
> + */
>  #define CE_UPDATE    (0x10000)
>  #define CE_REMOVE    (0x20000)
>  #define CE_UPTODATE  (0x40000)
> @@ -140,6 +168,24 @@ struct cache_entry {
>  #define CE_UNHASHED  (0x200000)
>  
>  /*
> + * Extended on-disk flags
> + */
> +/* CE_EXTENDED2 is for future extension */
> +#define CE_EXTENDED2 0x80000000

Perhaps CE_RESERVED then?

> +
> +#define CE_EXTENDED_FLAGS (0)
> +
> +/*
> + * Safeguard to avoid saving wrong flags:
> + *  - CE_EXTENDED2 won't get saved until its semantic is known
> + *  - Bits in 0x0000FFFF have been saved in ce_flags already
> + *  - Bits in 0x003F0000 are currently in-memory flags
> + */
> +#if CE_EXTENDED_FLAGS & 0x80CFFFFF
> +#error "CE_EXTENDED_FLAGS out of range"
> +#endif

I don't quite understand the above fragment (especially with the fact
that CE_EXTENDED_FLAGS is defined as (0))...

> diff --git a/read-cache.c b/read-cache.c
> index c5a8659..667c36b 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -1096,7 +1096,7 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
>  
>  	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
>  		return error("bad signature");
> -	if (hdr->hdr_version != htonl(2))
> +	if (hdr->hdr_version != htonl(2) && hdr->hdr_version != htonl(3))
>  		return error("bad index version");

By the way: what was index version 1?

[...]
-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH 01/14] Extend index to save more flags

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> By the way: what was index version 1?

It was the format used before ccc4feb (Convert the index file
reading/writing to use network byte order., 2005-04-15)

Re: [PATCH 01/14] Extend index to save more flags

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Jakub Narebski <jnareb@gmail.com> writes:
>
>> By the way: what was index version 1?
>
> It was the format used before ccc4feb (Convert the index file
> reading/writing to use network byte order., 2005-04-15)

Sorry, I dug that wrong.  The right one is:

ca9be05 (Make the sha1 of the index file go at the very end of the file., 2005-04-20)

Re: [PATCH 01/14] Extend index to save more flags

[Nguyen Thai Ngoc Duy]

On 9/21/08, Jakub Narebski <jnareb@gmail.com> wrote:
>  > +
>  > +#define CE_EXTENDED_FLAGS (0)
>  > +
>  > +/*
>  > + * Safeguard to avoid saving wrong flags:
>  > + *  - CE_EXTENDED2 won't get saved until its semantic is known
>  > + *  - Bits in 0x0000FFFF have been saved in ce_flags already
>  > + *  - Bits in 0x003F0000 are currently in-memory flags
>  > + */
>  > +#if CE_EXTENDED_FLAGS & 0x80CFFFFF
>  > +#error "CE_EXTENDED_FLAGS out of range"
>  > +#endif
>
>
> I don't quite understand the above fragment (especially with the fact
>  that CE_EXTENDED_FLAGS is defined as (0))...

Because this patch does not introduce any new on-disk flag yet so
CE_EXTENDED_FLAGS remains 0. In the next patch, CE_EXTENDED_FLAGS will
be updated to have CE_NO_CHECKOUT.
-- 
Duy

Re: [PATCH 01/14] Extend index to save more flags

[Jakub Narebski]

On Sun, 21 Sep 2008, Nguyen Thai Ngoc Duy wrote:
> On 9/21/08, Jakub Narebski <jnareb@gmail.com> wrote:
> > > +
> > > +#define CE_EXTENDED_FLAGS (0)
> > > +
> > > +/*
> > > + * Safeguard to avoid saving wrong flags:
> > > + *  - CE_EXTENDED2 won't get saved until its semantic is known
> > > + *  - Bits in 0x0000FFFF have been saved in ce_flags already
> > > + *  - Bits in 0x003F0000 are currently in-memory flags
> > > + */
> > > +#if CE_EXTENDED_FLAGS & 0x80CFFFFF
> > > +#error "CE_EXTENDED_FLAGS out of range"
> > > +#endif
> >
> >
> > I don't quite understand the above fragment (especially with the fact
> >  that CE_EXTENDED_FLAGS is defined as (0))...
> 
> Because this patch does not introduce any new on-disk flag yet so
> CE_EXTENDED_FLAGS remains 0. In the next patch, CE_EXTENDED_FLAGS will
> be updated to have CE_NO_CHECKOUT.

Well, now I understand CE_EXTENDED_FLAGS being (0).

What I still don't understand the pattern it is protected against.  
As I understand it if CE_EXTENDED_FLAGS & 0x0000FFFF it is bad,
because ce_flags saved flags are not extended flags, and 
CE_EXTENDED_FLAGS & 0x003F0000 are in-memory flags.  But why
CE_EXTENDED_FLAGS & 0x80C00000 is bad, and why (if I understand it)
CE_EXTENDED_FLAGS & 0x00300000 is not bad.

-- 
Jakub Narebski
Poland

Re: [PATCH 01/14] Extend index to save more flags

[Jakub Narebski]

On Mon, 22 Sep 2008, Duy Nguyen wrote:
> On 09/22/2008 "Jakub Narebski" <jnareb@gmail.com> wrote:
>>On Sun, 21 Sep 2008, Nguyen Thai Ngoc Duy wrote:
>>> On 9/21/08, Jakub Narebski <jnareb@gmail.com> wrote:
>>>>> +
>>>>> +#define CE_EXTENDED_FLAGS (0)
>>>>> +
>>>>> +/*
>>>>> + * Safeguard to avoid saving wrong flags:
>>>>> + *  - CE_EXTENDED2 won't get saved until its semantic is known
>>>>> + *  - Bits in 0x0000FFFF have been saved in ce_flags already
>>>>> + *  - Bits in 0x003F0000 are currently in-memory flags
>>>>> + */
>>>>> +#if CE_EXTENDED_FLAGS & 0x80CFFFFF
>>>>> +#error "CE_EXTENDED_FLAGS out of range"
>>>>> +#endif
>>>>
>>>>
>>>> I don't quite understand the above fragment (especially with the fact
>>>>  that CE_EXTENDED_FLAGS is defined as (0))...
>>> 
>>> Because this patch does not introduce any new on-disk flag yet so
>>> CE_EXTENDED_FLAGS remains 0. In the next patch, CE_EXTENDED_FLAGS will
>>> be updated to have CE_NO_CHECKOUT.
>> 
>> Well, now I understand CE_EXTENDED_FLAGS being (0).
>> 
>> What I still don't understand the pattern it is protected against.  
>> As I understand it if CE_EXTENDED_FLAGS & 0x0000FFFF it is bad,
>> because ce_flags saved flags are not extended flags, and 
>> CE_EXTENDED_FLAGS & 0x003F0000 are in-memory flags.  But why
>> CE_EXTENDED_FLAGS & 0x80C00000 is bad, and why (if I understand it)
>> CE_EXTENDED_FLAGS & 0x00300000 is not bad.
> 
> Wrong bit computation, should be "#if CE_EXTENDED_FLAGS & 0x803FFFFF".
> Thanks for pointing out. 

So now there is:

Now CE_EXTENDED_FLAGS & 0x803FFFFF is bad because:
  * CE_EXTENDED_FLAGS & 0x0000FFFF are saved flags (not extended)
  * CE_EXTENDED_FLAGS & 0x003F0000 are in-memory flags
  * CE_EXTENDED_FLAGS & 0x80000000 is 'extra flags' bit
    (this is not mentioned in quoted comment; I'm not sure if
     it needs to be or not)

Is that correct?
-- 
Jakub Narebski
Poland

Re: [PATCH 01/14] Extend index to save more flags

[Nguyen Thai Ngoc Duy]

On 9/28/08, Jakub Narebski <jnareb@gmail.com> wrote:
> So now there is:
>
>  Now CE_EXTENDED_FLAGS & 0x803FFFFF is bad because:
>   * CE_EXTENDED_FLAGS & 0x0000FFFF are saved flags (not extended)
>
>   * CE_EXTENDED_FLAGS & 0x003F0000 are in-memory flags
>
>   * CE_EXTENDED_FLAGS & 0x80000000 is 'extra flags' bit
>     (this is not mentioned in quoted comment; I'm not sure if
>      it needs to be or not)
>
>  Is that correct?

Correct.
-- 
Duy