[PATCH] mru: Replace mru.[ch] with list.h implementation

[PATCH] mru: Replace mru.[ch] with list.h implementation

[Gargi Sharma]

Replace custom allocation in mru.[ch] with generic calls
to list.h API.

Signed-off-by: Gargi Sharma <gs051095@gmail.com>
---
 builtin/pack-objects.c | 14 ++++++++------
 cache.h                |  9 +++++----
 mru.c                  | 27 ---------------------------
 mru.h                  | 40 ----------------------------------------
 packfile.c             | 28 +++++++++++++++++++---------
 5 files changed, 32 insertions(+), 86 deletions(-)
 delete mode 100644 mru.c
 delete mode 100644 mru.h

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index ba81234..26717c5 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -24,7 +24,7 @@
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
-#include "mru.h"
+#include "list.h"
 #include "packfile.h"
 
 static const char *pack_usage[] = {
@@ -1012,9 +1012,9 @@ static int want_object_in_pack(const unsigned char *sha1,
 			return want;
 	}
 
-	list_for_each(pos, &packed_git_mru.list) {
-		struct mru *entry = list_entry(pos, struct mru, list);
-		struct packed_git *p = entry->item;
+	list_for_each(pos, &packed_git_mru) {
+		struct packed_git *p = list_entry(pos, struct packed_git, mru);
+		struct list_head *entry = &(p->mru);
 		off_t offset;
 
 		if (p == *found_pack)
@@ -1030,8 +1030,10 @@ static int want_object_in_pack(const unsigned char *sha1,
 				*found_pack = p;
 			}
 			want = want_found_object(exclude, p);
-			if (!exclude && want > 0)
-				mru_mark(&packed_git_mru, entry);
+			if (!exclude && want > 0) {
+				list_del(entry);
+				list_add(entry, &packed_git_mru);
+			}
 			if (want != -1)
 				return want;
 		}
diff --git a/cache.h b/cache.h
index 49b083e..1a275ae 100644
--- a/cache.h
+++ b/cache.h
@@ -4,7 +4,7 @@
 #include "git-compat-util.h"
 #include "strbuf.h"
 #include "hashmap.h"
-#include "mru.h"
+#include "list.h"
 #include "advice.h"
 #include "gettext.h"
 #include "convert.h"
@@ -1566,6 +1566,7 @@ struct pack_window {
 
 extern struct packed_git {
 	struct packed_git *next;
+	struct list_head mru;
 	struct pack_window *windows;
 	off_t pack_size;
 	const void *index_data;
@@ -1587,10 +1588,10 @@ extern struct packed_git {
 } *packed_git;
 
 /*
- * A most-recently-used ordered version of the packed_git list, which can
- * be iterated instead of packed_git (and marked via mru_mark).
+ * A most-recently-used ordered version of the packed_git list.
  */
-extern struct mru packed_git_mru;
+extern struct list_head packed_git_mru;
+
 
 struct pack_entry {
 	off_t offset;
diff --git a/mru.c b/mru.c
deleted file mode 100644
index 8f3f34c..0000000
--- a/mru.c
+++ /dev/null
@@ -1,27 +0,0 @@
-#include "cache.h"
-#include "mru.h"
-
-void mru_append(struct mru *head, void *item)
-{
-	struct mru *cur = xmalloc(sizeof(*cur));
-	cur->item = item;
-	list_add_tail(&cur->list, &head->list);
-}
-
-void mru_mark(struct mru *head, struct mru *entry)
-{
-	/* To mark means to put at the front of the list. */
-	list_del(&entry->list);
-	list_add(&entry->list, &head->list);
-}
-
-void mru_clear(struct mru *head)
-{
-	struct list_head *pos;
-	struct list_head *tmp;
-
-	list_for_each_safe(pos, tmp, &head->list) {
-		free(list_entry(pos, struct mru, list));
-	}
-	INIT_LIST_HEAD(&head->list);
-}
diff --git a/mru.h b/mru.h
deleted file mode 100644
index 80a589e..0000000
--- a/mru.h
+++ /dev/null
@@ -1,40 +0,0 @@
-#ifndef MRU_H
-#define MRU_H
-
-#include "list.h"
-
-/**
- * A simple most-recently-used cache, backed by a doubly-linked list.
- *
- * Usage is roughly:
- *
- *   // Create a list.  Zero-initialization is required.
- *   static struct mru cache;
- *   INIT_LIST_HEAD(&cache.list);
- *
- *   // Add new item to the end of the list.
- *   void *item;
- *   ...
- *   mru_append(&cache, item);
- *
- *   // Mark an item as used, moving it to the front of the list.
- *   mru_mark(&cache, item);
- *
- *   // Reset the list to empty, cleaning up all resources.
- *   mru_clear(&cache);
- *
- * Note that you SHOULD NOT call mru_mark() and then continue traversing the
- * list; it reorders the marked item to the front of the list, and therefore
- * you will begin traversing the whole list again.
- */
-
-struct mru {
-	struct list_head list;
-	void *item;
-};
-
-void mru_append(struct mru *head, void *item);
-void mru_mark(struct mru *head, struct mru *entry);
-void mru_clear(struct mru *head);
-
-#endif /* MRU_H */
diff --git a/packfile.c b/packfile.c
index 502d915..3882d0b 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1,5 +1,5 @@
 #include "cache.h"
-#include "mru.h"
+#include "list.h"
 #include "pack.h"
 #include "dir.h"
 #include "mergesort.h"
@@ -40,7 +40,7 @@ static unsigned int pack_max_fds;
 static size_t peak_pack_mapped;
 static size_t pack_mapped;
 struct packed_git *packed_git;
-struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}};
+LIST_HEAD(packed_git_mru);
 
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
@@ -859,9 +859,18 @@ static void prepare_packed_git_mru(void)
 {
 	struct packed_git *p;
 
-	mru_clear(&packed_git_mru);
-	for (p = packed_git; p; p = p->next)
-		mru_append(&packed_git_mru, p);
+	struct list_head *pos;
+	struct list_head *tmp;
+	list_for_each_safe(pos, tmp, &packed_git_mru)
+		list_del_init(pos);
+
+	INIT_LIST_HEAD(&packed_git_mru);
+
+	for (p = packed_git; p; p = p->next) {
+		struct packed_git *cur = xmalloc(sizeof(*packed_git));
+		cur = p;
+		list_add_tail(&cur->mru, &packed_git_mru);
+	}
 }
 
 static int prepare_packed_git_run_once = 0;
@@ -1830,10 +1839,11 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 	if (!packed_git)
 		return 0;
 
-	list_for_each(pos, &packed_git_mru.list) {
-		struct mru *p = list_entry(pos, struct mru, list);
-		if (fill_pack_entry(sha1, e, p->item)) {
-			mru_mark(&packed_git_mru, p);
+	list_for_each(pos, &packed_git_mru) {
+		struct packed_git *p = list_entry(pos, struct packed_git, mru);
+		if (fill_pack_entry(sha1, e, p)) {
+			list_del(&p->mru);
+			list_add(&p->mru, &packed_git_mru);
 			return 1;
 		}
 	}
-- 
2.7.4

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Jeff King]

On Sat, Nov 11, 2017 at 01:06:46PM -0500, Gargi Sharma wrote:

> Replace custom allocation in mru.[ch] with generic calls
> to list.h API.
> 
> Signed-off-by: Gargi Sharma <gs051095@gmail.com>

Thanks, and welcome to the git list. :)

This looks like a good start on the topic, but I have a few comments.

It's a good idea to explain in the commit message not just what we're
doing, but why we want to do it, to help later readers of "git log". I
know that you picked this up from the discussion in the thread at:

  https://public-inbox.org/git/xmqq8tgz13x7.fsf@gitster.mtv.corp.google.com/

so it might be a good idea to summarize the ideas there (and add your
own thoughts, of course).

> ---
>  builtin/pack-objects.c | 14 ++++++++------
>  cache.h                |  9 +++++----
>  mru.c                  | 27 ---------------------------
>  mru.h                  | 40 ----------------------------------------
>  packfile.c             | 28 +++++++++++++++++++---------
>  5 files changed, 32 insertions(+), 86 deletions(-)
>  delete mode 100644 mru.c
>  delete mode 100644 mru.h

After the "---" line, you can put any information that people on the
list might want to know but that doesn't need to go into the commit
message. The big thing the maintainer would want to know here is that
your patch is prepared on top of the ot/mru-on-list topic, so he knows
where to apply it.

The diffstat is certainly encouraging so far. :)

> @@ -1012,9 +1012,9 @@ static int want_object_in_pack(const unsigned char *sha1,
>  			return want;
>  	}
>  
> -	list_for_each(pos, &packed_git_mru.list) {
> -		struct mru *entry = list_entry(pos, struct mru, list);
> -		struct packed_git *p = entry->item;
> +	list_for_each(pos, &packed_git_mru) {
> +		struct packed_git *p = list_entry(pos, struct packed_git, mru);
> +		struct list_head *entry = &(p->mru);
>  		off_t offset;
>  
>  		if (p == *found_pack)

I think "entry" here is going to be the same as "pos". That said, I
think it's only use is in bumping us to the front of the mru list later:

> @@ -1030,8 +1030,10 @@ static int want_object_in_pack(const unsigned char *sha1,
>  				*found_pack = p;
>  			}
>  			want = want_found_object(exclude, p);
> -			if (!exclude && want > 0)
> -				mru_mark(&packed_git_mru, entry);
> +			if (!exclude && want > 0) {
> +				list_del(entry);
> +				list_add(entry, &packed_git_mru);
> +			}

And I think this might be more obvious if we drop "entry" entirely and
just do:

  list_del(&p->mru);
  list_add(&p->mru, &packed_git_mru);

It might merit a comment like "/* bump to the front of the mru list */"
or similar to make it clear what's going on (or even adding a
list_move_to_front() helper).

> @@ -1566,6 +1566,7 @@ struct pack_window {
>  
>  extern struct packed_git {
>  	struct packed_git *next;
> +	struct list_head mru;
>  	struct pack_window *windows;
>  	off_t pack_size;
>  	const void *index_data;

Sort of a side note, but seeing these two list pointers together makes
me wonder what we should do with the list created by the "next" pointer.
It seems like there are three options:

  1. Convert it to "struct list_head", too, for consistency.

  2. Leave it as-is. We never delete from the list nor do any fancy
     manipulation, so it doesn't benefit from the reusable code.

  3. I wonder if we could drop it entirely, and just keep a single list
     of packs, ordered by mru. I'm not sure if anybody actually cares
     about accessing them in the "original" order. That order is
     reverse-chronological (by prepare_packed_git()), but I think that
     was mostly out of a sense that recent packs would be accessed more
     than older ones (but having a real mru strategy replaces that
     anyway).

What do you think?

> diff --git a/mru.c b/mru.c
> deleted file mode 100644
> index 8f3f34c..0000000

Yay, this hunk (and the one for mru.h) is satisfying.

> @@ -40,7 +40,7 @@ static unsigned int pack_max_fds;
>  static size_t peak_pack_mapped;
>  static size_t pack_mapped;
>  struct packed_git *packed_git;
> -struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}};
> +LIST_HEAD(packed_git_mru);

Much nicer.

> @@ -859,9 +859,18 @@ static void prepare_packed_git_mru(void)
>  {
>  	struct packed_git *p;
>  
> -	mru_clear(&packed_git_mru);
> -	for (p = packed_git; p; p = p->next)
> -		mru_append(&packed_git_mru, p);
> +	struct list_head *pos;
> +	struct list_head *tmp;
> +	list_for_each_safe(pos, tmp, &packed_git_mru)
> +		list_del_init(pos);

This matches the original code, which did the clear/re-create, resetting
the mru to the "original" pack order. But I do wonder if that's actually
necessary. Could we skip that and just add any new packs to the list?

That goes hand-in-hand with the idea of dropping the "next" pointer that
I mentioned above.

> +	INIT_LIST_HEAD(&packed_git_mru);

I think this INIT_LIST_HEAD() isn't necessary anymore. In the original
code, we just freed each of the mru_entry structs, which meant we had to
forcibly reset the list head to be empty. But here you've used
list_del_init(), so after deleting everything, packed_git_mru should
already be empty.

> +	for (p = packed_git; p; p = p->next) {
> +		struct packed_git *cur = xmalloc(sizeof(*packed_git));
> +		cur = p;
> +		list_add_tail(&cur->mru, &packed_git_mru);
> +	}

This malloc can go away. The original mru code kept a separate entry,
but now we don't need that. So here you're just leaking it when you
assign "cur = p" (in fact, I think you can get rid of cur entirely).

> @@ -1830,10 +1839,11 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
>  	if (!packed_git)
>  		return 0;
>  
> -	list_for_each(pos, &packed_git_mru.list) {
> -		struct mru *p = list_entry(pos, struct mru, list);
> -		if (fill_pack_entry(sha1, e, p->item)) {
> -			mru_mark(&packed_git_mru, p);
> +	list_for_each(pos, &packed_git_mru) {
> +		struct packed_git *p = list_entry(pos, struct packed_git, mru);
> +		if (fill_pack_entry(sha1, e, p)) {
> +			list_del(&p->mru);
> +			list_add(&p->mru, &packed_git_mru);
>  			return 1;
>  		}
>  	}

And this hunk looks pretty good (though if we added a move-to-front
helper, it could be used here, too).

-Peff

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Jeff King]

On Sun, Nov 12, 2017 at 09:54:35AM +0000, Jeff King wrote:

> > @@ -1566,6 +1566,7 @@ struct pack_window {
> >  
> >  extern struct packed_git {
> >  	struct packed_git *next;
> > +	struct list_head mru;
> >  	struct pack_window *windows;
> >  	off_t pack_size;
> >  	const void *index_data;
> 
> Sort of a side note, but seeing these two list pointers together makes
> me wonder what we should do with the list created by the "next" pointer.
> It seems like there are three options:
> 
>   1. Convert it to "struct list_head", too, for consistency.
> 
>   2. Leave it as-is. We never delete from the list nor do any fancy
>      manipulation, so it doesn't benefit from the reusable code.
> 
>   3. I wonder if we could drop it entirely, and just keep a single list
>      of packs, ordered by mru. I'm not sure if anybody actually cares
>      about accessing them in the "original" order. That order is
>      reverse-chronological (by prepare_packed_git()), but I think that
>      was mostly out of a sense that recent packs would be accessed more
>      than older ones (but having a real mru strategy replaces that
>      anyway).
> 
> What do you think?

Thinking on this a bit more, even if we want to go down any road except
(2), it probably ought to come as a separate patch on top anyway. The
changes you're making here are quite obviously a noop for visible
behavior.

But dropping the "next" pointer (and the matching "don't clear the list"
I mentioned later) would potentially mean examining the packs in a
slightly different order. I _think_ that's fine, but it's possible there
could be a subtle fallout. So it's better to keep it separate from the
more pure refactoring in your patch.

-Peff

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Gargi Sharma]

On Sun, Nov 12, 2017 at 9:54 AM, Jeff King <peff@peff.net> wrote:
> On Sat, Nov 11, 2017 at 01:06:46PM -0500, Gargi Sharma wrote:
>
>> Replace custom allocation in mru.[ch] with generic calls
>> to list.h API.
>>
>> Signed-off-by: Gargi Sharma <gs051095@gmail.com>
>
> Thanks, and welcome to the git list. :)
>
> This looks like a good start on the topic, but I have a few comments.
>
> It's a good idea to explain in the commit message not just what we're
> doing, but why we want to do it, to help later readers of "git log". I
> know that you picked this up from the discussion in the thread at:
>
>   https://public-inbox.org/git/xmqq8tgz13x7.fsf@gitster.mtv.corp.google.com/
>
> so it might be a good idea to summarize the ideas there (and add your
> own thoughts, of course).
>
>> ---
>>  builtin/pack-objects.c | 14 ++++++++------
>>  cache.h                |  9 +++++----
>>  mru.c                  | 27 ---------------------------
>>  mru.h                  | 40 ----------------------------------------
>>  packfile.c             | 28 +++++++++++++++++++---------
>>  5 files changed, 32 insertions(+), 86 deletions(-)
>>  delete mode 100644 mru.c
>>  delete mode 100644 mru.h
>
> After the "---" line, you can put any information that people on the
> list might want to know but that doesn't need to go into the commit
> message. The big thing the maintainer would want to know here is that
> your patch is prepared on top of the ot/mru-on-list topic, so he knows
> where to apply it.
>
> The diffstat is certainly encouraging so far. :)
>
>> @@ -1012,9 +1012,9 @@ static int want_object_in_pack(const unsigned char *sha1,
>>                       return want;
>>       }
>>
>> -     list_for_each(pos, &packed_git_mru.list) {
>> -             struct mru *entry = list_entry(pos, struct mru, list);
>> -             struct packed_git *p = entry->item;
>> +     list_for_each(pos, &packed_git_mru) {
>> +             struct packed_git *p = list_entry(pos, struct packed_git, mru);
>> +             struct list_head *entry = &(p->mru);
>>               off_t offset;
>>
>>               if (p == *found_pack)
>
> I think "entry" here is going to be the same as "pos". That said, I
> think it's only use is in bumping us to the front of the mru list later:
>
>> @@ -1030,8 +1030,10 @@ static int want_object_in_pack(const unsigned char *sha1,
>>                               *found_pack = p;
>>                       }
>>                       want = want_found_object(exclude, p);
>> -                     if (!exclude && want > 0)
>> -                             mru_mark(&packed_git_mru, entry);
>> +                     if (!exclude && want > 0) {
>> +                             list_del(entry);
>> +                             list_add(entry, &packed_git_mru);
>> +                     }
>
> And I think this might be more obvious if we drop "entry" entirely and
> just do:
>
>   list_del(&p->mru);
>   list_add(&p->mru, &packed_git_mru);
>
> It might merit a comment like "/* bump to the front of the mru list */"
> or similar to make it clear what's going on (or even adding a
> list_move_to_front() helper).

I will add a helper to list.h, for doing this :)
>
>> @@ -1566,6 +1566,7 @@ struct pack_window {
>>
>>  extern struct packed_git {
>>       struct packed_git *next;
>> +     struct list_head mru;
>>       struct pack_window *windows;
>>       off_t pack_size;
>>       const void *index_data;
>
> Sort of a side note, but seeing these two list pointers together makes
> me wonder what we should do with the list created by the "next" pointer.
> It seems like there are three options:
>
>   1. Convert it to "struct list_head", too, for consistency.
>
>   2. Leave it as-is. We never delete from the list nor do any fancy
>      manipulation, so it doesn't benefit from the reusable code.
>
>   3. I wonder if we could drop it entirely, and just keep a single list
>      of packs, ordered by mru. I'm not sure if anybody actually cares
>      about accessing them in the "original" order. That order is
>      reverse-chronological (by prepare_packed_git()), but I think that
>      was mostly out of a sense that recent packs would be accessed more
>      than older ones (but having a real mru strategy replaces that
>      anyway).
>
> What do you think?
I think in the long run, it'll be easier if there is only a single
list of packs given
that no one needs to access the list in order.

If we go down road 1/3, would it be better if I sent an entirely
different patch or
a patch series with patch 1 as removing mru[.ch] and patch 2 as removing
next pointer from the struct?

>
>> diff --git a/mru.c b/mru.c
>> deleted file mode 100644
>> index 8f3f34c..0000000
>
> Yay, this hunk (and the one for mru.h) is satisfying.
>
>> @@ -40,7 +40,7 @@ static unsigned int pack_max_fds;
>>  static size_t peak_pack_mapped;
>>  static size_t pack_mapped;
>>  struct packed_git *packed_git;
>> -struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}};
>> +LIST_HEAD(packed_git_mru);
>
> Much nicer.
>
>> @@ -859,9 +859,18 @@ static void prepare_packed_git_mru(void)
>>  {
>>       struct packed_git *p;
>>
>> -     mru_clear(&packed_git_mru);
>> -     for (p = packed_git; p; p = p->next)
>> -             mru_append(&packed_git_mru, p);
>> +     struct list_head *pos;
>> +     struct list_head *tmp;
>> +     list_for_each_safe(pos, tmp, &packed_git_mru)
>> +             list_del_init(pos);
>
> This matches the original code, which did the clear/re-create, resetting
> the mru to the "original" pack order. But I do wonder if that's actually
> necessary. Could we skip that and just add any new packs to the list?

But if we do not clear the older entries from the list, wouldn't there be a
problem when you access packed_git_mru->next, since that will be populated
instead of being empty? Or am I misunderstanding something here?

>
> That goes hand-in-hand with the idea of dropping the "next" pointer that
> I mentioned above.
>
>> +     INIT_LIST_HEAD(&packed_git_mru);
>
> I think this INIT_LIST_HEAD() isn't necessary anymore. In the original
> code, we just freed each of the mru_entry structs, which meant we had to
> forcibly reset the list head to be empty. But here you've used
> list_del_init(), so after deleting everything, packed_git_mru should
> already be empty.
>
>> +     for (p = packed_git; p; p = p->next) {
>> +             struct packed_git *cur = xmalloc(sizeof(*packed_git));
>> +             cur = p;
>> +             list_add_tail(&cur->mru, &packed_git_mru);
>> +     }
>
> This malloc can go away. The original mru code kept a separate entry,
> but now we don't need that. So here you're just leaking it when you
> assign "cur = p" (in fact, I think you can get rid of cur entirely).

Ah yes, I'll fix this.

>
>> @@ -1830,10 +1839,11 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
>>       if (!packed_git)
>>               return 0;
>>
>> -     list_for_each(pos, &packed_git_mru.list) {
>> -             struct mru *p = list_entry(pos, struct mru, list);
>> -             if (fill_pack_entry(sha1, e, p->item)) {
>> -                     mru_mark(&packed_git_mru, p);
>> +     list_for_each(pos, &packed_git_mru) {
>> +             struct packed_git *p = list_entry(pos, struct packed_git, mru);
>> +             if (fill_pack_entry(sha1, e, p)) {
>> +                     list_del(&p->mru);
>> +                     list_add(&p->mru, &packed_git_mru);
>>                       return 1;
>>               }
>>       }
>
> And this hunk looks pretty good (though if we added a move-to-front
> helper, it could be used here, too).

Thanks!
gargi
>
> -Peff

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Jeff King]

On Sun, Nov 12, 2017 at 12:49:17PM +0000, Gargi Sharma wrote:

> > Sort of a side note, but seeing these two list pointers together makes
> > me wonder what we should do with the list created by the "next" pointer.
> > It seems like there are three options:
> >
> >   1. Convert it to "struct list_head", too, for consistency.
> >
> >   2. Leave it as-is. We never delete from the list nor do any fancy
> >      manipulation, so it doesn't benefit from the reusable code.
> >
> >   3. I wonder if we could drop it entirely, and just keep a single list
> >      of packs, ordered by mru. I'm not sure if anybody actually cares
> >      about accessing them in the "original" order. That order is
> >      reverse-chronological (by prepare_packed_git()), but I think that
> >      was mostly out of a sense that recent packs would be accessed more
> >      than older ones (but having a real mru strategy replaces that
> >      anyway).
> >
> > What do you think?
> I think in the long run, it'll be easier if there is only a single
> list of packs given
> that no one needs to access the list in order.

Yeah, it's that "given..." that makes me just a little nervous that I'm
missing something.

> If we go down road 1/3, would it be better if I sent an entirely
> different patch or
> a patch series with patch 1 as removing mru[.ch] and patch 2 as removing
> next pointer from the struct?

I think you could do it as a 2-patch series like that, or you could send
the first patch now (since I think it stands on its own merits) and do
the other one later on top.

> > This matches the original code, which did the clear/re-create, resetting
> > the mru to the "original" pack order. But I do wonder if that's actually
> > necessary. Could we skip that and just add any new packs to the list?
> 
> But if we do not clear the older entries from the list, wouldn't there be a
> problem when you access packed_git_mru->next, since that will be populated
> instead of being empty? Or am I misunderstanding something here?

What I mean is that instead of clearing and re-adding all of the packs
(including any new ones we picked up by rescanning the directory), we
would _just_ add new ones to the list.

So I think we'd scrap this whole "set up the mru" preparation here and
just teach install_packed_git() to add the new pack to the MRU list.

-Peff

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Оля Тележная]

Gargi,
If you have some difficulties - please feel free to ask questions
(here or you can write me directly). I will be happy to help you.
As I understand, you are super close to finish your first patch.

Olga

[PATCH] mru: Replace mru.[ch] with list.h implementation

[Gargi Sharma]

Replace the custom calls to mru.[ch] with calls to list.h. This patch is the
final step in removing the mru API completely and inlining the logic.

Another discussion, here
(https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)
was on what has to be done with the next pointer of packed git type
inside the
packed_git structure. It can be removed _given_ that no one needs to
access the list in order and can be sent as another patch.

---
Changes in v2:
        - Add a move to front function to the list API.
        - Remove memory leak.
        - Remove redundant remove operations on the list.

The commit has been built on top of ot/mru-on-list branch.

 Makefile               |  1 -
 builtin/pack-objects.c | 12 ++++++------
 cache.h                |  9 +++++----
 list.h                 |  7 +++++++
 mru.c                  | 27 ---------------------------
 mru.h                  | 40 ----------------------------------------
 packfile.c             | 18 +++++++++---------
 sha1_file.c            |  1 -
 8 files changed, 27 insertions(+), 88 deletions(-)
 delete mode 100644 mru.c
 delete mode 100644 mru.h

diff --git a/Makefile b/Makefile
index ed4ca43..4a79ec5 100644
--- a/Makefile
+++ b/Makefile
@@ -814,7 +814,6 @@ LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
-LIB_OBJS += mru.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index ba81234..4064e35 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -24,7 +24,7 @@
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
-#include "mru.h"
+#include "list.h"
 #include "packfile.h"
 
 static const char *pack_usage[] = {
@@ -1012,9 +1012,8 @@ static int want_object_in_pack(const unsigned char *sha1,
 			return want;
 	}
 
-	list_for_each(pos, &packed_git_mru.list) {
-		struct mru *entry = list_entry(pos, struct mru, list);
-		struct packed_git *p = entry->item;
+	list_for_each(pos, &packed_git_mru) {
+		struct packed_git *p = list_entry(pos, struct packed_git, mru);
 		off_t offset;
 
 		if (p == *found_pack)
@@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,
 				*found_pack = p;
 			}
 			want = want_found_object(exclude, p);
-			if (!exclude && want > 0)
-				mru_mark(&packed_git_mru, entry);
+			if (!exclude && want > 0) {
+				list_move_to_front(&p->mru, &packed_git_mru);
+			}
 			if (want != -1)
 				return want;
 		}
diff --git a/cache.h b/cache.h
index 49b083e..1a275ae 100644
--- a/cache.h
+++ b/cache.h
@@ -4,7 +4,7 @@
 #include "git-compat-util.h"
 #include "strbuf.h"
 #include "hashmap.h"
-#include "mru.h"
+#include "list.h"
 #include "advice.h"
 #include "gettext.h"
 #include "convert.h"
@@ -1566,6 +1566,7 @@ struct pack_window {
 
 extern struct packed_git {
 	struct packed_git *next;
+	struct list_head mru;
 	struct pack_window *windows;
 	off_t pack_size;
 	const void *index_data;
@@ -1587,10 +1588,10 @@ extern struct packed_git {
 } *packed_git;
 
 /*
- * A most-recently-used ordered version of the packed_git list, which can
- * be iterated instead of packed_git (and marked via mru_mark).
+ * A most-recently-used ordered version of the packed_git list.
  */
-extern struct mru packed_git_mru;
+extern struct list_head packed_git_mru;
+
 
 struct pack_entry {
 	off_t offset;
diff --git a/list.h b/list.h
index eb60119..5129b0a 100644
--- a/list.h
+++ b/list.h
@@ -93,6 +93,13 @@ static inline void list_move(struct list_head *elem, struct list_head *head)
 	list_add(elem, head);
 }
 
+/* Move to the front of the list. */
+static inline void list_move_to_front(struct list_head *elem, struct list_head *head)
+{
+	list_del(elem);
+	list_add(elem, head);
+}
+
 /* Replace an old entry. */
 static inline void list_replace(struct list_head *old, struct list_head *newp)
 {
diff --git a/mru.c b/mru.c
deleted file mode 100644
index 8f3f34c..0000000
--- a/mru.c
+++ /dev/null
@@ -1,27 +0,0 @@
-#include "cache.h"
-#include "mru.h"
-
-void mru_append(struct mru *head, void *item)
-{
-	struct mru *cur = xmalloc(sizeof(*cur));
-	cur->item = item;
-	list_add_tail(&cur->list, &head->list);
-}
-
-void mru_mark(struct mru *head, struct mru *entry)
-{
-	/* To mark means to put at the front of the list. */
-	list_del(&entry->list);
-	list_add(&entry->list, &head->list);
-}
-
-void mru_clear(struct mru *head)
-{
-	struct list_head *pos;
-	struct list_head *tmp;
-
-	list_for_each_safe(pos, tmp, &head->list) {
-		free(list_entry(pos, struct mru, list));
-	}
-	INIT_LIST_HEAD(&head->list);
-}
diff --git a/mru.h b/mru.h
deleted file mode 100644
index 80a589e..0000000
--- a/mru.h
+++ /dev/null
@@ -1,40 +0,0 @@
-#ifndef MRU_H
-#define MRU_H
-
-#include "list.h"
-
-/**
- * A simple most-recently-used cache, backed by a doubly-linked list.
- *
- * Usage is roughly:
- *
- *   // Create a list.  Zero-initialization is required.
- *   static struct mru cache;
- *   INIT_LIST_HEAD(&cache.list);
- *
- *   // Add new item to the end of the list.
- *   void *item;
- *   ...
- *   mru_append(&cache, item);
- *
- *   // Mark an item as used, moving it to the front of the list.
- *   mru_mark(&cache, item);
- *
- *   // Reset the list to empty, cleaning up all resources.
- *   mru_clear(&cache);
- *
- * Note that you SHOULD NOT call mru_mark() and then continue traversing the
- * list; it reorders the marked item to the front of the list, and therefore
- * you will begin traversing the whole list again.
- */
-
-struct mru {
-	struct list_head list;
-	void *item;
-};
-
-void mru_append(struct mru *head, void *item);
-void mru_mark(struct mru *head, struct mru *entry);
-void mru_clear(struct mru *head);
-
-#endif /* MRU_H */
diff --git a/packfile.c b/packfile.c
index 502d915..0a25cf2 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1,5 +1,5 @@
 #include "cache.h"
-#include "mru.h"
+#include "list.h"
 #include "pack.h"
 #include "dir.h"
 #include "mergesort.h"
@@ -40,7 +40,7 @@ static unsigned int pack_max_fds;
 static size_t peak_pack_mapped;
 static size_t pack_mapped;
 struct packed_git *packed_git;
-struct mru packed_git_mru = {{&packed_git_mru.list, &packed_git_mru.list}};
+LIST_HEAD(packed_git_mru);
 
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
@@ -859,9 +859,9 @@ static void prepare_packed_git_mru(void)
 {
 	struct packed_git *p;
 
-	mru_clear(&packed_git_mru);
-	for (p = packed_git; p; p = p->next)
-		mru_append(&packed_git_mru, p);
+	for (p = packed_git; p; p = p->next) {
+		list_add_tail(&p->mru, &packed_git_mru);
+	}
 }
 
 static int prepare_packed_git_run_once = 0;
@@ -1830,10 +1830,10 @@ int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 	if (!packed_git)
 		return 0;
 
-	list_for_each(pos, &packed_git_mru.list) {
-		struct mru *p = list_entry(pos, struct mru, list);
-		if (fill_pack_entry(sha1, e, p->item)) {
-			mru_mark(&packed_git_mru, p);
+	list_for_each(pos, &packed_git_mru) {
+		struct packed_git *p = list_entry(pos, struct packed_git, mru);
+		if (fill_pack_entry(sha1, e, p)) {
+			list_move_to_front(&p->mru, &packed_git_mru);
 			return 1;
 		}
 	}
diff --git a/sha1_file.c b/sha1_file.c
index 5a20148..e664f2d 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -24,7 +24,6 @@
 #include "bulk-checkin.h"
 #include "streaming.h"
 #include "dir.h"
-#include "mru.h"
 #include "list.h"
 #include "mergesort.h"
 #include "quote.h"
-- 
2.7.4

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Christian Couder]

On Tue, Jan 16, 2018 at 2:46 AM, Gargi Sharma <gs051095@gmail.com> wrote:
> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the
> final step in removing the mru API completely and inlining the logic.

You might want to say that this provides a significant code reduction
which shows that the mru API is not a very useful abstraction anymore.

> Another discussion, here
> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)
> was on what has to be done with the next pointer of packed git type

I think using "pointer to a 'struct packed_git'" instead of "pointer
of packed git type" would be clearer here, but anyway see below.

> inside the
> packed_git structure. It can be removed _given_ that no one needs to
> access the list in order and can be sent as another patch.

I don't think it's worth pointing to a discussion about a future
improvement in the commit message. You could perhaps even remove all
the above paragraph as this commit is valuable and self contained
enough by itself.

> ---
> Changes in v2:
>         - Add a move to front function to the list API.
>         - Remove memory leak.
>         - Remove redundant remove operations on the list.
>
> The commit has been built on top of ot/mru-on-list branch.

Nice!

>  Makefile               |  1 -
>  builtin/pack-objects.c | 12 ++++++------
>  cache.h                |  9 +++++----
>  list.h                 |  7 +++++++
>  mru.c                  | 27 ---------------------------
>  mru.h                  | 40 ----------------------------------------
>  packfile.c             | 18 +++++++++---------
>  sha1_file.c            |  1 -
>  8 files changed, 27 insertions(+), 88 deletions(-)
>  delete mode 100644 mru.c
>  delete mode 100644 mru.h

Very nice!

[...]

> @@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,
>                                 *found_pack = p;
>                         }
>                         want = want_found_object(exclude, p);
> -                       if (!exclude && want > 0)
> -                               mru_mark(&packed_git_mru, entry);
> +                       if (!exclude && want > 0) {
> +                               list_move_to_front(&p->mru, &packed_git_mru);
> +                       }

Style: we usually remove brackets when there is one line after the
if(...) line. (See the 2 lines that you delete.)

Otherwise the patch looks good to me.

Thanks,
Christian.

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> On Tue, Jan 16, 2018 at 2:46 AM, Gargi Sharma <gs051095@gmail.com> wrote:
>> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the
>> final step in removing the mru API completely and inlining the logic.
>
> You might want to say that this provides a significant code reduction
> which shows that the mru API is not a very useful abstraction anymore.
>
>> Another discussion, here
>> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)
>> was on what has to be done with the next pointer of packed git type
>
> I think using "pointer to a 'struct packed_git'" instead of "pointer
> of packed git type" would be clearer here, but anyway see below.
>
>> inside the
>> packed_git structure. It can be removed _given_ that no one needs to
>> access the list in order and can be sent as another patch.
>
> I don't think it's worth pointing to a discussion about a future
> improvement in the commit message. You could perhaps even remove all
> the above paragraph as this commit is valuable and self contained
> enough by itself.

True. 

If it is summarizing conclusion of the earlier discussion, that is a
different matter, though.

It is perfectly OK to have it under "---" line, even if it is merely
voicing author's opinion, by the way.  It can serve as a good
discussion (re-)starter.


>> ---

Missing sign-off?

>> Changes in v2:
>>         - Add a move to front function to the list API.
>>         - Remove memory leak.
>>         - Remove redundant remove operations on the list.
>>
>> The commit has been built on top of ot/mru-on-list branch.
>
> Nice!
>
>>  Makefile               |  1 -
>>  builtin/pack-objects.c | 12 ++++++------
>>  cache.h                |  9 +++++----
>>  list.h                 |  7 +++++++
>>  mru.c                  | 27 ---------------------------
>>  mru.h                  | 40 ----------------------------------------
>>  packfile.c             | 18 +++++++++---------
>>  sha1_file.c            |  1 -
>>  8 files changed, 27 insertions(+), 88 deletions(-)
>>  delete mode 100644 mru.c
>>  delete mode 100644 mru.h
>
> Very nice!

Yes, nice reduction.

>
> [...]
>
>> @@ -1030,8 +1029,9 @@ static int want_object_in_pack(const unsigned char *sha1,
>>                                 *found_pack = p;
>>                         }
>>                         want = want_found_object(exclude, p);
>> -                       if (!exclude && want > 0)
>> -                               mru_mark(&packed_git_mru, entry);
>> +                       if (!exclude && want > 0) {
>> +                               list_move_to_front(&p->mru, &packed_git_mru);
>> +                       }
>
> Style: we usually remove brackets when there is one line after the
> if(...) line. (See the 2 lines that you delete.)
>
> Otherwise the patch looks good to me.
>
> Thanks,
> Christian.

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Jeff King]

On Mon, Jan 15, 2018 at 08:46:25PM -0500, Gargi Sharma wrote:

> Replace the custom calls to mru.[ch] with calls to list.h. This patch is the
> final step in removing the mru API completely and inlining the logic.
> 
> Another discussion, here
> (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)
> was on what has to be done with the next pointer of packed git type
> inside the
> packed_git structure. It can be removed _given_ that no one needs to
> access the list in order and can be sent as another patch.

Thanks for picking this up again. I agree that this is probably a good
stopping point for now, as I think just combining this with the 'next'
pointer may carry more side effects.

Aside from the braces thing that Christian mentioned (and the missing
signoff), this all looks good to me.

-Peff

Re: [PATCH] mru: Replace mru.[ch] with list.h implementation

[Gargi Sharma]

On Fri, Jan 19, 2018 at 9:46 PM, Jeff King <peff@peff.net> wrote:
>
> On Mon, Jan 15, 2018 at 08:46:25PM -0500, Gargi Sharma wrote:
>
> > Replace the custom calls to mru.[ch] with calls to list.h. This patch is the
> > final step in removing the mru API completely and inlining the logic.
> >
> > Another discussion, here
> > (https://public-inbox.org/git/CAOCi2DGYQr4jFf5ObY2buyhNJeaAPQKF8tbojn2W0b18Eo+Wgw@mail.gmail.com/)
> > was on what has to be done with the next pointer of packed git type
> > inside the
> > packed_git structure. It can be removed _given_ that no one needs to
> > access the list in order and can be sent as another patch.
>
> Thanks for picking this up again. I agree that this is probably a good
> stopping point for now, as I think just combining this with the 'next'
> pointer may carry more side effects.
Agreed, hence just thought that if the discussion is started again, we
can point them
to the email thread.
>
> Aside from the braces thing that Christian mentioned (and the missing
> signoff), this all looks good to me.
Thanks, made the changes and sent a v3,

Best,
Gargi
>
> -Peff