1. 06 Sep, 2017 1 commit
    • Jeff King's avatar
      tempfile: use list.h for linked list · 24d82185
      Jeff King authored
      The tempfile API keeps to-be-cleaned tempfiles in a
      singly-linked list and never removes items from the list.  A
      future patch would like to start removing items, but removal
      from a singly linked list is O(n), as we have to walk the
      list to find the predecessor element. This means that a
      process which takes "n" simultaneous lockfiles (for example,
      an atomic transaction on "n" refs) may end up quadratic in
      Before we start allowing items to be removed, it would be
      nice to have a way to cover this case in linear time.
      The simplest solution is to make an assumption about the
      order in which tempfiles are added and removed from the
      list. If both operations iterate over the tempfiles in the
      same order, then by putting new items at the end of the list
      our removal search will always find its items at the
      beginning of the list. And indeed, that would work for the
      case of refs. But it creates a hidden dependency between
      unrelated parts of the code. If anybody changes the ref code
      (or if we add a new caller that opens multiple simultaneous
      tempfiles) they may unknowingly introduce a performance
      Another solution is to use a better data structure. A
      doubly-linked list works fine, and we already have an
      implementation in list.h. But there's one snag: the elements
      of "struct tempfile" are all marked as "volatile", since a
      signal handler may interrupt us and iterate over the list at
      any moment (even if we were in the middle of adding a new
      We can declare a "volatile struct list_head", but we can't
      actually use it with the normal list functions. The compiler
      complains about passing a pointer-to-volatile via a regular
      pointer argument. And rightfully so, as the sub-function
      would potentially need different code to deal with the
      volatile case.
      That leaves us with a few options:
        1. Drop the "volatile" modifier for the list items.
           This is probably a bad idea. I checked the assembly
           output from "gcc -O2", and the "volatile" really does
           impact the order in which it updates memory.
        2. Use macros instead of inline functions. The irony here
           is that list.h is entirely implemented as trivial
           inline functions. So we basically are already
           generating custom code for each call. But sadly there's no
           way in C to declare the inline function to take a more
           generic type.
           We could do so by switching the inline functions to
           macros, but it does make the end result harder to read.
           And it doesn't fully solve the problem (for instance,
           the declaration of list_head needs to change so that
           its "prev" and "next" pointers point to other volatile
        3. Don't use list.h, and just make our own ad-hoc
           doubly-linked list. It's not that much code to
           implement the basics that we need here. But if we're
           going to do so, why not add the few extra lines
           required to model it after the actual list.h interface?
           We can even reuse a few of the macro helpers.
      So this patch takes option 3, but actually implements a
      parallel "volatile list" interface in list.h, where it could
      potentially be reused by other code. This implements just
      enough for tempfile.c's use, though we could easily port
      other functions later if need be.
      Signed-off-by: default avatarJeff King <peff@peff.net>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
  2. 18 Jul, 2016 1 commit
  3. 12 Jul, 2016 1 commit
    • Eric Wong's avatar
      http-walker: reduce O(n) ops with doubly-linked list · 94e99012
      Eric Wong authored
      Using the a Linux-kernel-derived doubly-linked list
      implementation from the Userspace RCU library allows us to
      enqueue and delete items from the object request queue in
      constant time.
      This change reduces enqueue times in the prefetch() function
      where object request queue could grow to several thousand
      I left out the list_for_each_entry* family macros from list.h
      which relied on the __typeof__ operator as we support platforms
      without it.  Thus, list_entry (aka "container_of") needs to be
      called explicitly inside macro-wrapped for loops.
      The downside is this costs us an additional pointer per object
      request, but this is offset by reduced overhead on queue
      operations leading to improved performance and shorter queue
      Signed-off-by: default avatarEric Wong <e@80x24.org>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>