git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Brandon Williams <bmwill@google.com>
To: Jeff King <peff@peff.net>
Cc: Michael Haggerty <mhagger@alum.mit.edu>,
	Lars Schneider <larsxschneider@gmail.com>,
	Martin Ågren <martin.agren@gmail.com>,
	Git Users <git@vger.kernel.org>
Subject: Re: [PATCH] config: use a static lock_file struct
Date: Wed, 30 Aug 2017 12:57:31 -0700
Message-ID: <20170830195731.GB50018@google.com> (raw)
In-Reply-To: <20170830195320.27w5mhnrcd2uosvz@sigill.intra.peff.net>

On 08/30, Jeff King wrote:
> On Wed, Aug 30, 2017 at 08:55:01AM +0200, Michael Haggerty wrote:
> 
> > > +	tempfile->active = 0;
> > > +	for (p = &tempfile_list; *p; p = &(*p)->next) {
> > > +		if (*p == tempfile) {
> > > +			*p = tempfile->next;
> > > +			break;
> > > +		}
> > >  	}
> > >  }
> > 
> > `deactivate_tempfile()` is O(N) in the number of active tempfiles. This
> > could get noticeable for, say, updating 30k references, which involves
> > obtaining 30k reference locks. I think that code adds the locks in
> > alphabetical order and also removes them in alphabetical order, so the
> > overall effort would go like O(N²). I'm guessing that this would be
> > measurable but not fatal for realistic numbers of references, but it
> > should at least be benchmarked.
> > 
> > There are three obvious ways to make this O(1) again:
> > 
> > * Make the list doubly-linked.
> 
> Yeah, I noticed this when writing it, and the doubly-linked list was my
> first thought. It's much more straight-forward than making guesses about
> traversal order, and we already have a nice implementation in list.h.

I agree that a doubly-linked list is probably the best way to go in
order to solve the performance issue.

> 
> What made me hesitate for this demonstration was that it turns the
> removal into _two_ pointer updates. That made me more nervous about the
> racy case where we get a single handler while already deleting
> something. Specifically when we have "a <-> b <-> c" and we've updated
> "a->next" to point to "c" but "c->prev" still points to "b".
> 
> But even with the singly-linked list we're not fully race-proof
> (somebody could set *p to NULL between the time we look at it and
> dereference it). What we really care about is not two versions of the
> function running simultaneously, but one version getting interrupted by
> another and having the second one see a sane state (because we'll never
> return to the first signal handler; the second one will raise() and
> die).
> 
> And I think we're fine there even with a doubly-linked list. It's still
> the single update of the "next" pointer that controls that second
> traversal.
> 
> -Peff

I know it was mentioned earlier but if this is a critical section, and
it would be bad if it was interrupted, then couldn't we turn off
interrupts before attempting to remove an item from the list?

-- 
Brandon Williams

  reply index

Thread overview: 40+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-08-27  7:37 [PATCH] pkt-line: re-'static'-ify buffer in packet_write_fmt_1() Martin Ågren
2017-08-27 15:41 ` Jeff King
2017-08-27 18:25   ` Jeff King
2017-08-27 18:21 ` Lars Schneider
2017-08-27 19:09   ` Martin Ågren
2017-08-27 19:15     ` Jeff King
2017-08-27 20:04     ` Lars Schneider
2017-08-27 23:23       ` Jeff King
2017-08-28  4:11         ` Martin Ågren
2017-08-28 17:52           ` Stefan Beller
2017-08-28 17:58             ` Jeff King
2017-09-05 10:03               ` Junio C Hamano
2017-08-29 17:51           ` Lars Schneider
2017-08-29 18:53             ` Jeff King
2017-08-29 18:58               ` [PATCH] config: use a static lock_file struct Jeff King
2017-08-29 19:09                 ` Brandon Williams
2017-08-29 19:10                   ` Brandon Williams
2017-08-29 19:12                   ` Jeff King
2017-08-30  3:25                     ` Michael Haggerty
2017-08-30  4:31                       ` Jeff King
2017-08-30  4:55                         ` Michael Haggerty
2017-08-30  4:55                         ` Jeff King
2017-08-30  5:55                           ` Jeff King
2017-08-30  7:07                             ` Michael Haggerty
2017-09-02  8:44                               ` Jeff King
2017-09-02 13:50                                 ` Jeff King
2017-08-30  6:55                           ` Michael Haggerty
2017-08-30 19:53                             ` Jeff King
2017-08-30 19:57                               ` Brandon Williams [this message]
2017-08-30 20:11                                 ` Jeff King
2017-08-30 21:06                                   ` Brandon Williams
2017-08-31  4:09                                     ` Jeff King
2017-09-06  3:59                 ` Junio C Hamano
2017-09-06 12:41                   ` Jeff King
2017-08-29 19:22               ` [PATCH] pkt-line: re-'static'-ify buffer in packet_write_fmt_1() Martin Ågren
2017-08-29 21:48                 ` Jeff King
2017-08-30  5:31                   ` Jeff King
2017-09-05 10:03                     ` Junio C Hamano
2017-10-10  4:06                       ` [PATCH 0/2] Do not call cmd_*() as a subroutine Junio C Hamano
2017-10-10  4:06                         ` [PATCH 1/2] describe: do not use " Junio C Hamano
2017-10-10  4:06                         ` [PATCH 2/2] merge-ours: " Junio C Hamano

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20170830195731.GB50018@google.com \
    --to=bmwill@google.com \
    --cc=git@vger.kernel.org \
    --cc=larsxschneider@gmail.com \
    --cc=martin.agren@gmail.com \
    --cc=mhagger@alum.mit.edu \
    --cc=peff@peff.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox