patch[Outreachy] cleanup: use list.h in mru.h and mru.c

Remove implementation of double-linked list in mru.c and mru.h and use implementation from list.h.

Signed-off-by: Olga Telezhnaia <olyatelezhnaya@gmail.com>
Mentored-by: Christian Couder <christian.couder@gmail.com>, Jeff King
<peff@peff.net>
---
 builtin/pack-objects.c |  5 +++--
 mru.c                  | 51 +++++++++++++++-----------------------------------
 mru.h                  | 31 +++++++++++++-----------------
 packfile.c             |  6 ++++--
 4 files changed, 35 insertions(+), 58 deletions(-)

About the title, we don't usually start with "fix:" or "cleanup:" or "feature:". We usually start with the (main) area of the code that is changed.

So maybe something like "mru: use double-linked list implementation from list.h" would be better.

On Wed, Sep 27, 2017 at 12:18 PM, Оля Тележная <olyatelezhnaya@gmail.com> wrote:

It is important in the commit message to get a good idea of the reason why the patch is a good thing. So for example "Simplify mru.c, mru.h and related code by reusing the double-linked list implementation from list.h instead of a custom one." could be a bit better.

I think it's better if Peff is on another "Mentored-by: ..." line.

Here we can see that saying that we simplify things is probably true as the patch deletes more lines than it adds.

It looks like there are indentation problems in the patch.

Did you try to send it to you and apply what you received?

When I try to apply it to master I get:

Applying: cleanup: use list.h in mru.h and mru.c
.git/rebase-apply/patch:18: indent with spaces.
        struct list_head *pos;
.git/rebase-apply/patch:152: indent with spaces.
        void *item;
error: patch failed: builtin/pack-objects.c:995
error: builtin/pack-objects.c: patch does not apply
error: patch failed: mru.c:1
error: mru.c: patch does not apply
error: patch failed: mru.h:8
error: mru.h: patch does not apply
error: patch failed: packfile.c:876
error: packfile.c: patch does not apply
Patch failed at 0001 cleanup: use list.h in mru.h and mru.c
The copy of the patch that failed is found in: .git/rebase-apply/patch
When you have resolved this problem, run "git am --continue".
If you prefer to skip this patch, run "git am --skip" instead.
To restore the original branch and stop patching, run "git am --abort".

I am stopping here as it's quite difficult to read patches that have indentation problems.

Simplify mru.c, mru.h and related code by reusing the double-linked list implementation from list.h instead of a custom one.

Signed-off-by: Olga Telezhnaia <olyatelezhnaya@gmail.com>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c |  5 +++--
 mru.c                  | 51 +++++++++++++++-----------------------------------
 mru.h                  | 31 +++++++++++++-----------------
 packfile.c             |  6 ++++--
 4 files changed, 35 insertions(+), 58 deletions(-)

Olga Telezhnaya <olyatelezhnaya@gmail.com> writes:

An overlong line (I can locally wrap it, so the patch does not have to be re-sent only to fix this alone).

Thanks for making your "From:" name match the "Signed-off-by:" name; anglicising like you did is probably more friendly to the readers than writing both in Cyrillic, which is another valid way to make them match.

As Christian mentioned earlier, nice line reduction ;-)

%> +++ b/builtin/pack-objects.c

I was a bit surprised to see a change outside mru.[ch] like this one. The reason why I was surprised was because I expected mru.[ch] would offer its own API that encapsulates enumeration like this one and this patch would just be reimplementing that API using the list API, instead of rewriting the users of mru API to directly access the list API.

Alas, there is no such mru API that lets a mru user to iterate over elements, so the original of the above code were using mru's implementation detail directly.

We probably want to invent mru_for_each() that hides the fact that mru is implemented in terms of list_head from the users of mru API and use it here.

"Zero-initialization is required." is no longer true, it seems, and the comment above needs to be updated, right?

More importantly, this leaks to the user of the API the fact that mru is internally implemented in terms of the list API, which is not necessary (when we want to update the implementation later, we'd need to update all the users again). Perhaps you'd want

	INIT_MRU(cache);

which is #define'd in this file, perhaps like so:

	#define INIT_MRU(mru)	INIT_LIST_HEAD(&((mru).list))

Ah, here is a good piece that illustrates what I meant earlier. This could have been something like:

	// Iterate in MRU order.
	struct mru *item;
	mru_for_each(item, &cache) {
		if (matches(item))
			break;
	}

and then the user would not have to know mru is implemented in terms of the list API.

The same comment as the first hunk applies here, too.

Thanks.

On Thu, Sep 28, 2017 at 08:03:00PM +0900, Junio C Hamano wrote:

I agree that the caller would be a little shorter with an mru-specific iterator (e.g., we could probably do the list_entry() part automatically).

But I also think this patch may be a stepping stone to dropping "struct mru" entirely, and just pushing a "struct list_head mru" into the packed_git object itself (or of course any object you like). At which point we'd just directly use the list iterators anyway.

(One could argue that if that's our end goal, we could go straight there. But I think this middle state has value, because the individual steps are easier to verify).

I'd make the same claims here as above (both that I agree your proposed interface looks nicer, but also that I think we eventually do want to expose that this is tightly coupled with list.h).

-Peff

Jeff King <peff@peff.net> writes:

The endgame state implied by your statement would mean that we won't have mru_mark() and instead have these open-coded in terms of the two calls into the list API. There only are two callers of it in the current system, so it is not the end of the world, so I guess I can agree that this is a good preparation step toward the longer term goal, which says "mru API is over-engineered and what it offers over the plain vanilla list API is almost never used except for a few callsite; let's remove it and use the bare list API instead".

I agree. I just do not yet know if I fully embrace the idea that we just should use bare list API, getting rid of the mru API.

On Fri, Sep 29, 2017 at 06:56:28AM +0900, Junio C Hamano wrote:

Thanks, that last sentence is a good summary of my thinking (I think what I find most silly about it is that it allocates a whole extra struct per item, which is where most of the complication comes from).

I had envisioned leaving mru_mark() as a wrapper for "move to the front" that could operate on any list. But seeing how Olga's patch takes it down to two trivial lines, I'd also be fine with an endgame that just eliminates it.

Fair enough.

-Peff

On Thu, Sep 28, 2017 at 08:38:39AM +0000, Olga Telezhnaya wrote:

The commit message is a good reason to talk about why we want to do this. In this case, the answer may be fairly obvious. But I sometimes find that things that are obvious to me as the patch author are not quite as obvious to people reading it later (either reviewing, or six months from now when they are hunting the cause of a bug).

Nice, this hunk is very satisfying. :)

Two minor style comments here:

  - Perhaps "tmp" is a better name than "p2" for the second argument of
    a list_for_each_safe, as it makes it less likely to confuse p1 and
    p2 (though admittedly the whole function is short enough that it
    probably doesn't matter much either way).

  - It's a good practice to declare variables in the smallest scope
    possible. So I think the declaration of to_free could go inside the
    loop.

    You could actually get rid of it entirely with:

      free(list_entry(p1, struct mru, list));

    but I certainly don't mind using a variable for better readability.

The decision to get rid of the "mru versus mru_entry" distinction surprised me a little. In the original, a "struct mru" represented the whole list. In the list.h implementation, a "struct list_head" serves that purpose, as a sentinel value. But that sentinel doesn't need to have an "item", right? I.e., we could have:

  struct mru {
          struct list_head head;
  };

  struct mru_entry {
          void *item;
	  struct list_head list;
  };

As I said in my response to Junio (and as we discussed a little off-list), I think we can eventually move to having no structs at all (just list_heads embedded inside the existing packfile objects). At which point the user of the API would just declare:

  LIST_HEAD(packed_git_mru);

themselves. So I'm actually fine with this direction if we're using it as the "middle step" that I mentioned there.

The funny indentation in this diff shows that "void *item" is indented with spaces, not a tab.

I pointed out a few minor bits, but overall this is looking very strong. Great work!

-Peff

On Thu, Sep 28, 2017 at 08:38:39AM +0000, Olga Telezhnaya wrote:

I was thinking on this hunk a bit more, and I think it's not quite right.

The prepare_packed_git_mru() function will clear the mru list and then re-add each item from the packed_git list. But by calling INIT_LIST_HEAD() here, we're effectively clearing the packed_git_mru list, and we end up leaking whatever was on the list before.

So for the first call to prepare_packed_git, we really need this INIT_LIST_HEAD() call. But for subsequent calls (which come from reprepare_packed_git()), we must not call it.

There are a few ways to work around it that I can think of:

  1. Check whether packed_git_mru.list.head is NULL, and only initialize
     in that case.

  2. Use a static initializer for packed_git_mru.list, so that we don't
     have do the first-time initializing here.

  3. Teach reprepare_packed_git() to do the mru_clear() call, so that we
     know the list is empty when we get here.

One final and more invasive option is to stop regenerating the packed_git_mru list from scratch during each prepare_packed_git(). I did it that way so that we start with the same order that rearrange_packed_git() will give us, but I'm not sure how much value that has in practice (it probably had a lot more when we didn't have the mru, and the time-sorted pack order helped find recent objects more quickly).

The alternative would be to just teach install_packed_git() to add each newly-added pack to the mru list, and then never clear the list (and we wouldn't need an mru_clear() at all, then).

-Peff

On Fri, Sep 29, 2017 at 12:42 AM, Jeff King <peff@peff.net> wrote:

The current code is:

static int prepare_packed_git_run_once = 0;
void prepare_packed_git(void)
{
    struct alternate_object_database *alt;

    if (prepare_packed_git_run_once)
        return;
    prepare_packed_git_one(get_object_directory(), 1);
    prepare_alt_odb();
    for (alt = alt_odb_list; alt; alt = alt->next)
        prepare_packed_git_one(alt->path, 0);
    rearrange_packed_git();
    prepare_packed_git_mru();
    prepare_packed_git_run_once = 1;
}

As we use the "prepare_packed_git_run_once" static, this function will only be called only once when packed_git_mru has not yet been initialized, so there will be no leak.

On Fri, Sep 29, 2017 at 09:18:11AM +0200, Christian Couder wrote:

Check reprepare_packed_git(). It unsets the run_once flag, and then calls prepare_packed_git() again.

-Peff

On Fri, Sep 29, 2017 at 9:23 AM, Jeff King <peff@peff.net> wrote:

Ah ok.

Hi everyone, Many thanks to all of you, I am interested in every opinion. Sorry that I wasn't in the discussion, unfortunately I got sick, that's why I skipped all the process. I want to reply to the main moments and also ask some questions.

I've read only about 50 characters max in commit head (and highlighting repeats it), but there's nothing about max length of line in commit message. Sorry, next time I will make it shorter.

About many different opinions how to improve the code: I agree with the idea that my commit is a middle step to get rid of MRU at all. If we really need to add initializer/mru_for_each/smth_else - it's absolutely not a problem, but as it was said, not sure that we need it. It really looks that using list implementation from list.h directly won't be worse.

Let's add needed function to list.h directly? I also wanted to add list_for_each_entry function to list.h as it's in Linux kernel. https://www.kernel.org/doc/htmldocs/kernel-api/API-list-for-each-entry.html It will simplify the code even more, guess that not only in MRU related code. Maybe we need to do that in separate patch.

About minor issues ( "tmp" vs "p2", variable scope, space indentation)
- fully agree, I will fix it.

So finally I think that I need to fix that minor issues and that's all. I have plans to rewrite (with --amend) my current commit (I think so because I will add no new features, so it's better to have single commit for all changes). As I understand, Submitgit will send an update in a new thread. And I need to say there [PATCH v2]. Please correct me if I am wrong in any of the moments mentioned earlier.

By the way, other contributors write smth like "[PATCH v6 0/3]". What does mean "0/3"? It's about editing separate commits in a single patch, am I right?

Thank you one more time! Olga

I forgot about leak. I also need to add checking in mru_clear. That's not beautiful solution but it works reliably. Question remains the same - do you see something more to fix in this patch?

Thank you! Olga

On Fri, Sep 29, 2017 at 11:38:27PM +0300, Оля Тележная wrote:

I'm not sure what you mean about checking in mru_clear(). It may make sense to just send your v2 patch and I can see there what you do.

I think that's it. Think about writing a bit in the commit message about the "why" of this. Like I said earlier, the rationale for this commit is perhaps obvious, but it never hurts to be explicit (and it may be good practice, since part of the point of this task is getting you familiar with the patch submission process).

-Peff

I added "v2" after "PATCH", but it does not appeared. Actually it was written automatically and it was "PATCH Outreachy v2". I rearranged it in the middle of the phrase.

I realized that I said something strange before. I solved the problem with leak by deleting INIT in prepare_packed_git and adding init as you suggested here: https://github.com/telezhnaya/git/commit/7f8995835949f83e54efdfd88445feb6d54cb3e9#commitcomment-24576103

By the way, I asked to edit FAQ for Linux kernel newbies about linked list that confused me a week ago, and that funny picture was deleted. https://kernelnewbies.org/FAQ/LinkedLists Maybe it will help to someone else :)

On Sat, Sep 30, 2017 at 09:09:11PM +0300, Оля Тележная wrote:

That looks fine.

OK, that makes sense.

Thank you. :)

Remember (and this applies to other Outreachy folks, too) to submit your application in the Outreachy system:

   https://outreachy.gnome.org

-Peff

On Fri, Sep 29, 2017 at 07:08:28PM +0300, Оля Тележная wrote:

No problem. It's often reasonable to let review comments come in and think about them as a whole before responding or re-posting anyway.

Usually we shoot for making things look good in an 80-column terminal, including both code and commit messages. For commit message bodies, we tend to make them a little shorter, since "git log" will indent them. 72 characters is reasonable there. And we tend to make subject lines a little shorter than that, even since they often appear with "Subject:" and "[PATCH]" prefixed. I usually go for about 60 characters, but will go over if it helps make the subject more clear.

Yes, I think we could just call this "list_move_to_front()" or something. The fact that it's operating on a list called "packed_git_mru" is probably sufficient to make it clear that the purpose is managing recentness.

It would be nice to have list_for_each_entry(), but unfortunately it's not portable. It relies on having a typeof operator, and we build on platforms that lack it. It was omitted in 94e99012fc (http-walker: reduce O(n) ops with doubly-linked list, 2016-07-11) for that reason.

Thanks.

Correct. Until a patch is merged to Junio's "next" branch (at which point it is set in stone), we generally prefer to rewrite it with "--amend" (or git-rebase) to fix anything that comes up during the review.

Right, it means multiple commits in a logical series that are meant to be applied together. Your patch is small enough that it makes as a single patch. If we wanted to do the second step of dropping mru.[ch] entirely now, then you'd probably have at least a 2-patch series.

(I'm OK with not doing that second step for now, though if we are not going to polish up the mru_for_each() interface, it may make sense to make the final step sooner rather than later).

-Peff

Jeff King <peff@peff.net> writes:

I earlier said I wasn't sure, but I fully agree with your envisioned endgame state, my understanding of which is that we will not have an API that is only to be used to manage a MRU list (hence there will be no mru.[ch] in that future), as there is very small MRU-specific operation to be offered anyway. Namely, mru_mark() that is to be used to "mark the fact that the item was used---do whatever necessary to maintain the MRU list".

Instead, everybody understands how the list API works, and the fact that one instance of list_head is called MRU is sufficient to see that use of "move this to the front of the list" function means we are marking the item as most-recently-used.

Thanks.

Simplify mru.[ch] and related code by reusing the double-linked list implementation from list.h instead of a custom one. This commit is an intermediate step. Our final goal is to get rid of mru.[ch] at all and inline all logic.

Signed-off-by: Olga Telezhnaia <olyatelezhnaya@gmail.com>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c |  5 +++--
 mru.c                  | 49 +++++++++++++------------------------------------
 mru.h                  | 31 +++++++++++++------------------
 packfile.c             |  7 ++++---
 4 files changed, 33 insertions(+), 59 deletions(-)

On Sat, Sep 30, 2017 at 05:51:01PM +0000, Olga Telezhnaya wrote:

Thanks, this version looks correct to me.

I do think there are a few ugly bits in the result (like that initializer for packed_git_mru :) ), so I'd prefer not to merge this down until we do that final step.

So the big question is: who wants to do it?

I think you've done a good job here, and this would count for your Outreachy application's contribution. But if you'd like to do that next step, you are welcome to.

We could also consider it a #leftoverbits that perhaps some other Outreachy candidate would pick up[1].

In the meantime, Junio, I think we'd want to queue this with the intent to graduate it to "pu" or possibly "next", but not "master". Then if somebody (Olga or another applicant) produces the endgame patch, we can queue it on top and move it further. And if nobody does, I can pick it after the application period is over.

-Peff

[1] For those who find this mail through the archive, there's more
    discussion in this thread:

      https://public-inbox.org/git/CAL21BmnvJSaN+Tnw7Hdc5P5biAnM5dfWR7gX5FrAG1r_D8th=A@mail.gmail.com/

Great! What is better - to complete my application now (and say only about this patch) or to complete it in last days (and say about everything that I've done. Maybe there would be something new).

I was thinking about starting my small research about main task of the internship. I could postpone it and end with this task, there's no problem for me. Or, if someone from the newbies wants to have a small simple task - it's a great opportunity for him/her. By the way, I am ready to help if he/she will have questions or difficulties. So please make a decision on your own, I will be happy in any scenario.

On Mon, Oct 02, 2017 at 12:37:53PM +0300, Оля Тележная wrote:

I think it's good to get it started now. You can always make changes to it later. And in particular, you should fill out the eligibility section s we can make sure that part is good before going further.

I do think you should spend some time thinking about and researching the main task. I'd hope to see in the applications that the candidate has a sense of the problem space and a realistic plan for approaching the work.

Wonderful. :) I do hope to get Outreachy interns involve in normal list activities like discussion and review, not just producing their own patches.

Why don't we give it a week or so to see if anybody else picks it up.

-Peff

Jeff King <peff@peff.net> writes:

So... do we still want to keep this in 'next', or does somebody wants to do honors?

I'd really prefer *not* to see you or me ending up finishing it up, but at the same time, I really hate seeing a halfway or 3/4 done topic hanging around in 'pu'.

On Wed, Nov 08, 2017 at 10:44:46AM +0900, Junio C Hamano wrote:

We hung back on it to leave it as low-hanging fruit for other Outreachy applicants. Perhaps Olga would like to pick it up now that the application period is over.

Alternatively, it might be a nice task for the Bloomberg hackathon this weekend. I'll add it to the list of topics there, too.

-Peff

It's absolutely not a problem for me, I can do that as one more warm-up exercise in the beginning of the internship.

Thanks!