Re: [PATCH 4/7] delta_base_cache: use list.h for LRU
On Mon, Aug 22, 2016 at 11:18:06PM +, Eric Wong wrote:
> > As a bonus, the list_entry() macro lets us place the lru
> > pointers anywhere inside the delta_base_cache_entry struct
> > (as opposed to just casting the pointer, which requires it
> > at the front of the struct). This will be useful in later
> > patches when we need to place other items at the front of
> > the struct (e.g., our hashmap implementation requires this).
>
> On a side note, I think we should s/list_entry/container_of/ and
> use container_of for hashmap.
>
> Linux kernel defines list_entry to use container_of,
> but I'd rather avoid introducing the duality entirely.
That does make it slightly more annoying to use, since container_of()
requires naming the original type again (because of our lack of typeof),
whereas now you can freely cast between "struct hashmap_entry" and the
actual item. But if you are proposing to actually fix the hashmap to
eliminate the requirement to put the entry at the front, that might have
value (I'm not sure how easy it is to do, though; a lot of those casts
happen inside the hashmap code which is type-agnostic).
> > Signed-off-by: Jeff King
> > ---
> > I think the result is much nicer, but I found list_entry() a little
> > disappointing, because we lack typeof(). So you are stuck writing:
> >
> > struct delta_base_cache_entry *f =
> > list_entry(p, struct delta_base_cache_entry, lru);
> >
> > I waffled on adding something like:
> >
> > LIST_ITEM(struct delta_bas_cache_entry, f, p, lru);
> >
> > to declare "f" as above. But it's getting rather magical and un-C-like.
>
> Right. I'd rather keep the list_entry/container_of usage
> identical to what developers familiar using userspace-rcu,
> ccan/list, or the Linux kernel expect.
Makes sense. I am not familiar with those APIs myself, but I do not see
any reason to deviate from them for no good reason.
> > sha1_file.c | 38 --
> > 1 file changed, 16 insertions(+), 22 deletions(-)
>
> Good to see the code reduction.
Yep. I realized the "hashmap must go at the front of the struct" thing
later. My initial reason for converting was actually to make the
"separate blob LRU" patch easier (since without this patch, it literally
doubles the amount of pointer manipulation required).
For reference, in case anybody wants to duplicate my experiments from
patch 5, that patch looks like this:
diff --git a/sha1_file.c b/sha1_file.c
index 2cd1b79..e82be30 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2076,7 +2076,8 @@ static void *unpack_compressed_entry(struct packed_git *p,
static size_t delta_base_cached;
-static LIST_HEAD(delta_base_cache_lru);
+static LIST_HEAD(delta_base_cache_lru_blobs);
+static LIST_HEAD(delta_base_cache_lru_other);
static struct delta_base_cache_entry {
struct list_head lru;
@@ -2170,15 +2171,14 @@ static void add_delta_base_cache(struct packed_git *p,
off_t base_offset,
release_delta_base_cache(ent);
delta_base_cached += base_size;
- list_for_each(lru, &delta_base_cache_lru) {
+ list_for_each(lru, &delta_base_cache_lru_blobs) {
struct delta_base_cache_entry *f =
list_entry(lru, struct delta_base_cache_entry, lru);
if (delta_base_cached <= delta_base_cache_limit)
break;
- if (f->type == OBJ_BLOB)
- release_delta_base_cache(f);
+ release_delta_base_cache(f);
}
- list_for_each(lru, &delta_base_cache_lru) {
+ list_for_each(lru, &delta_base_cache_lru_other) {
struct delta_base_cache_entry *f =
list_entry(lru, struct delta_base_cache_entry, lru);
if (delta_base_cached <= delta_base_cache_limit)
@@ -2191,7 +2191,10 @@ static void add_delta_base_cache(struct packed_git *p,
off_t base_offset,
ent->type = type;
ent->data = base;
ent->size = base_size;
- list_add_tail(&ent->lru, &delta_base_cache_lru);
+ if (type == OBJ_BLOB)
+ list_add_tail(&ent->lru, &delta_base_cache_lru_blobs);
+ else
+ list_add_tail(&ent->lru, &delta_base_cache_lru_other);
}
static void *read_object(const unsigned char *sha1, enum object_type *type,
-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/7] delta_base_cache: use list.h for LRU
Jeff King wrote: > We keep an LRU list of entries for when we need to drop > something from an over-full cache. The list is implemented > as a circular doubly-linked list, which is exactly what > list.h provides. We can save a few lines by using the list.h > macros and functions. More importantly, this makes the code > easier to follow, as the reader sees explicit concepts like > "list_add_tail()" instead of pointer manipulation. Yay! > As a bonus, the list_entry() macro lets us place the lru > pointers anywhere inside the delta_base_cache_entry struct > (as opposed to just casting the pointer, which requires it > at the front of the struct). This will be useful in later > patches when we need to place other items at the front of > the struct (e.g., our hashmap implementation requires this). On a side note, I think we should s/list_entry/container_of/ and use container_of for hashmap. Linux kernel defines list_entry to use container_of, but I'd rather avoid introducing the duality entirely. > Signed-off-by: Jeff King > --- > I think the result is much nicer, but I found list_entry() a little > disappointing, because we lack typeof(). So you are stuck writing: > > struct delta_base_cache_entry *f = > list_entry(p, struct delta_base_cache_entry, lru); > > I waffled on adding something like: > > LIST_ITEM(struct delta_bas_cache_entry, f, p, lru); > > to declare "f" as above. But it's getting rather magical and un-C-like. Right. I'd rather keep the list_entry/container_of usage identical to what developers familiar using userspace-rcu, ccan/list, or the Linux kernel expect. > sha1_file.c | 38 -- > 1 file changed, 16 insertions(+), 22 deletions(-) Good to see the code reduction. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 4/7] delta_base_cache: use list.h for LRU
We keep an LRU list of entries for when we need to drop
something from an over-full cache. The list is implemented
as a circular doubly-linked list, which is exactly what
list.h provides. We can save a few lines by using the list.h
macros and functions. More importantly, this makes the code
easier to follow, as the reader sees explicit concepts like
"list_add_tail()" instead of pointer manipulation.
As a bonus, the list_entry() macro lets us place the lru
pointers anywhere inside the delta_base_cache_entry struct
(as opposed to just casting the pointer, which requires it
at the front of the struct). This will be useful in later
patches when we need to place other items at the front of
the struct (e.g., our hashmap implementation requires this).
Signed-off-by: Jeff King
---
I think the result is much nicer, but I found list_entry() a little
disappointing, because we lack typeof(). So you are stuck writing:
struct delta_base_cache_entry *f =
list_entry(p, struct delta_base_cache_entry, lru);
I waffled on adding something like:
LIST_ITEM(struct delta_bas_cache_entry, f, p, lru);
to declare "f" as above. But it's getting rather magical and un-C-like.
sha1_file.c | 38 --
1 file changed, 16 insertions(+), 22 deletions(-)
diff --git a/sha1_file.c b/sha1_file.c
index 8264b39..c02e785 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -24,6 +24,7 @@
#include "streaming.h"
#include "dir.h"
#include "mru.h"
+#include "list.h"
#ifndef O_NOATIME
#if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -2077,13 +2078,10 @@ static void *unpack_compressed_entry(struct packed_git
*p,
static size_t delta_base_cached;
-static struct delta_base_cache_lru_list {
- struct delta_base_cache_lru_list *prev;
- struct delta_base_cache_lru_list *next;
-} delta_base_cache_lru = { &delta_base_cache_lru, &delta_base_cache_lru };
+static LIST_HEAD(delta_base_cache_lru);
static struct delta_base_cache_entry {
- struct delta_base_cache_lru_list lru;
+ struct list_head lru;
void *data;
struct packed_git *p;
off_t base_offset;
@@ -2128,8 +2126,7 @@ static int in_delta_base_cache(struct packed_git *p,
off_t base_offset)
static void detach_delta_base_cache_entry(struct delta_base_cache_entry *ent)
{
ent->data = NULL;
- ent->lru.next->prev = ent->lru.prev;
- ent->lru.prev->next = ent->lru.next;
+ list_del(&ent->lru);
delta_base_cached -= ent->size;
}
@@ -2168,24 +2165,24 @@ static void add_delta_base_cache(struct packed_git *p,
off_t base_offset,
{
unsigned long hash = pack_entry_hash(p, base_offset);
struct delta_base_cache_entry *ent = delta_base_cache + hash;
- struct delta_base_cache_lru_list *lru;
+ struct list_head *lru;
release_delta_base_cache(ent);
delta_base_cached += base_size;
- for (lru = delta_base_cache_lru.next;
-delta_base_cached > delta_base_cache_limit
-&& lru != &delta_base_cache_lru;
-lru = lru->next) {
- struct delta_base_cache_entry *f = (void *)lru;
+ list_for_each(lru, &delta_base_cache_lru) {
+ struct delta_base_cache_entry *f =
+ list_entry(lru, struct delta_base_cache_entry, lru);
+ if (delta_base_cached <= delta_base_cache_limit)
+ break;
if (f->type == OBJ_BLOB)
release_delta_base_cache(f);
}
- for (lru = delta_base_cache_lru.next;
-delta_base_cached > delta_base_cache_limit
-&& lru != &delta_base_cache_lru;
-lru = lru->next) {
- struct delta_base_cache_entry *f = (void *)lru;
+ list_for_each(lru, &delta_base_cache_lru) {
+ struct delta_base_cache_entry *f =
+ list_entry(lru, struct delta_base_cache_entry, lru);
+ if (delta_base_cached <= delta_base_cache_limit)
+ break;
release_delta_base_cache(f);
}
@@ -2194,10 +2191,7 @@ static void add_delta_base_cache(struct packed_git *p,
off_t base_offset,
ent->type = type;
ent->data = base;
ent->size = base_size;
- ent->lru.next = &delta_base_cache_lru;
- ent->lru.prev = delta_base_cache_lru.prev;
- delta_base_cache_lru.prev->next = &ent->lru;
- delta_base_cache_lru.prev = &ent->lru;
+ list_add_tail(&ent->lru, &delta_base_cache_lru);
}
static void *read_object(const unsigned char *sha1, enum object_type *type,
--
2.10.0.rc1.118.ge2299eb
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
