git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Michael Haggerty <mhagger@alum.mit.edu>
To: Jeff King <peff@peff.net>
Cc: Brandon Williams <bmwill@google.com>,
	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 08:55:01 +0200
Message-ID: <3e632fd3-7db9-4c38-c524-b56a06cfaa87@alum.mit.edu> (raw)
In-Reply-To: <20170830045555.27xczwo3ql7q4bg3@sigill.intra.peff.net>

On 08/30/2017 06:55 AM, Jeff King wrote:
> [...]
> Something like this, which AFAICT is about as safe as the existing code
> in its list manipulation. It retains the "active" flag as an additional
> check which I think isn't strictly necessary, but potentially catches
> some logic errors.
> 
> The strbuf_reset() calls become strbuf_release(), since we're promising
> the caller that they could now free the struct (or let it go out of
> scope) if they chose. Probably during a signal handler we should skip
> that (we know the struct is off the list and non-active at that point,
> but we could possibly hit libc's free() mutex).

This looks OK to me aside from the one caveat below.

> diff --git a/tempfile.c b/tempfile.c
> index 6843710670..a7d964ebf8 100644
> --- a/tempfile.c
> +++ b/tempfile.c
> [...]
> +static void deactivate_tempfile(struct tempfile *tempfile)
> +{
> +	struct tempfile *volatile *p;
> +
> +	if (!tempfile->active)
> +		return;
> +
> +	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.
* Make sure that all significant callers remove items in the *reverse*
order that they were added, in which case the item to be removed would
always be found near the head of the list.
* Change this class to keep track of a tail pointer and add new items at
the end of the list, and ensure that all significant callers remove
locks in the *same* order that they were added.

The second and third options might be easy or difficult (depend on how
much current callers need to be changed) and certainly would be easy to
break again as new callers are added in the future.

> [...]

Michael

  parent 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 [this message]
2017-08-30 19:53                             ` Jeff King
2017-08-30 19:57                               ` Brandon Williams
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=3e632fd3-7db9-4c38-c524-b56a06cfaa87@alum.mit.edu \
    --to=mhagger@alum.mit.edu \
    --cc=bmwill@google.com \
    --cc=git@vger.kernel.org \
    --cc=larsxschneider@gmail.com \
    --cc=martin.agren@gmail.com \
    --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