<feed xmlns='http://www.w3.org/2005/Atom'>
<title>delta/libgit2.git/src/cache.c, branch ethomson/github_actions</title>
<subtitle>github.com: libgit2/libgit2.git
</subtitle>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/'/>
<entry>
<title>tree-wide: remove unused functions</title>
<updated>2020-06-08T19:17:57+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2020-06-08T10:39:09+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=7c499b544dc3383cce38956f86d67f328bc718e6'/>
<id>7c499b544dc3383cce38956f86d67f328bc718e6</id>
<content type='text'>
We have some functions which aren't used anywhere. Let's remove them to
get rid of unneeded baggage.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
We have some functions which aren't used anywhere. Let's remove them to
get rid of unneeded baggage.
</pre>
</div>
</content>
</entry>
<entry>
<title>cache: fix invalid memory access in case updating cache entry fails</title>
<updated>2020-02-07T12:08:23+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2020-02-07T11:50:39+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=7d1b17744a958890cae4648d4b38de2999832d77'/>
<id>7d1b17744a958890cae4648d4b38de2999832d77</id>
<content type='text'>
When adding a new entry to our cache where an entry with the same OID
exists already, then we only update the existing entry in case it is
unparsed and the new entry is parsed. Currently, we do not check the
return value of `git_oidmap_set` though when updating the existing
entry. As a result, we will _not_ have updated the existing entry if
`git_oidmap_set` fails, but have decremented its refcount and
incremented the new entry's refcount. Later on, this may likely lead to
dereferencing invalid memory.

Fix the issue by checking the return value of `git_oidmap_set`. In case
it fails, we will simply keep the existing stored instead, even though
it's unparsed.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
When adding a new entry to our cache where an entry with the same OID
exists already, then we only update the existing entry in case it is
unparsed and the new entry is parsed. Currently, we do not check the
return value of `git_oidmap_set` though when updating the existing
entry. As a result, we will _not_ have updated the existing entry if
`git_oidmap_set` fails, but have decremented its refcount and
incremented the new entry's refcount. Later on, this may likely lead to
dereferencing invalid memory.

Fix the issue by checking the return value of `git_oidmap_set`. In case
it fails, we will simply keep the existing stored instead, even though
it's unparsed.
</pre>
</div>
</content>
</entry>
<entry>
<title>cache: evict items more efficiently</title>
<updated>2019-07-17T15:59:54+00:00</updated>
<author>
<name>brian m. carlson</name>
<email>bk2204@github.com</email>
</author>
<published>2019-07-17T15:59:54+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=770b91b114467c5e6b7d3edc884e0fef6475c0bc'/>
<id>770b91b114467c5e6b7d3edc884e0fef6475c0bc</id>
<content type='text'>
When our object cache is full, we pick eight items (or the whole cache,
if there are fewer) and evict them. For small cache sizes, this is fine,
but when we're dealing with a large number of objects, we can repeatedly
exhaust the cache and spend a large amount of time in git_oidmap_iterate
trying to find items to evict.

Instead, let's assume that if the cache gets full, we have a large
number of objects that we're handling, and be more aggressive about
evicting items. Let's remove one item for every 2048 items, but not less
than 8. This causes us to scale our evictions in proportion to the size
of the cache and significantly reduces the time we spend in
git_oidmap_iterate.

Before this change, a full pack of all the non-blob objects in the Linux
repository took in excess of 30 minutes and spent 62.3% of total runtime
in odb_read_1 and its children, and 44.3% of the time in
git_oidmap_iterate. With this change, the same operation now takes 14
minutes and 44 seconds, and odb_read_1 accounts for only 35.9% of total
time, whereas git_oidmap_iterate consists of 6.2%.

Note that we do spend a little more time inflating objects and a decent
amount more time in memcmp. However, overall, the time taken is
significantly improved, and time in pack building is now dominated by
git_delta_create_from_index (33.7%), which is what we would expect.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
When our object cache is full, we pick eight items (or the whole cache,
if there are fewer) and evict them. For small cache sizes, this is fine,
but when we're dealing with a large number of objects, we can repeatedly
exhaust the cache and spend a large amount of time in git_oidmap_iterate
trying to find items to evict.

Instead, let's assume that if the cache gets full, we have a large
number of objects that we're handling, and be more aggressive about
evicting items. Let's remove one item for every 2048 items, but not less
than 8. This causes us to scale our evictions in proportion to the size
of the cache and significantly reduces the time we spend in
git_oidmap_iterate.

Before this change, a full pack of all the non-blob objects in the Linux
repository took in excess of 30 minutes and spent 62.3% of total runtime
in odb_read_1 and its children, and 44.3% of the time in
git_oidmap_iterate. With this change, the same operation now takes 14
minutes and 44 seconds, and odb_read_1 accounts for only 35.9% of total
time, whereas git_oidmap_iterate consists of 6.2%.

Note that we do spend a little more time inflating objects and a decent
amount more time in memcmp. However, overall, the time taken is
significantly improved, and time in pack building is now dominated by
git_delta_create_from_index (33.7%), which is what we would expect.
</pre>
</div>
</content>
</entry>
<entry>
<title>cache: fix cache eviction using deallocated key</title>
<updated>2019-05-24T13:28:33+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2019-05-24T13:24:26+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=add1743580149c3d1e570aafff3180cee216162e'/>
<id>add1743580149c3d1e570aafff3180cee216162e</id>
<content type='text'>
When evicting cache entries, we first retrieve the object that is
to be evicted, delete the object and then finally delete the key
from the cache. In case where the cache eviction caused us to
free the cached object, though, its key will point to invalid
memory now when trying to remove it from the cache map. On my
system, this causes us to not properly remove the key from the
map, as its memory has been overwritten already and thus the key
lookup it will fail and we cannot delete it.

Fix this by only decrementing the refcount of the evictee after
we have removed it from our cache map. Add a test that caused a
segfault previous to that change.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
When evicting cache entries, we first retrieve the object that is
to be evicted, delete the object and then finally delete the key
from the cache. In case where the cache eviction caused us to
free the cached object, though, its key will point to invalid
memory now when trying to remove it from the cache map. On my
system, this causes us to not properly remove the key from the
map, as its memory has been overwritten already and thus the key
lookup it will fail and we cannot delete it.

Fix this by only decrementing the refcount of the evictee after
we have removed it from our cache map. Add a test that caused a
segfault previous to that change.
</pre>
</div>
</content>
</entry>
<entry>
<title>Merge pull request #4901 from pks-t/pks/uniform-map-api</title>
<updated>2019-02-22T10:56:08+00:00</updated>
<author>
<name>Edward Thomson</name>
<email>ethomson@edwardthomson.com</email>
</author>
<published>2019-02-22T10:56:08+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=4069f924855d596871a7e1f16c5c3f67a16dd5f4'/>
<id>4069f924855d596871a7e1f16c5c3f67a16dd5f4</id>
<content type='text'>
High-level map APIs</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
High-level map APIs</pre>
</div>
</content>
</entry>
<entry>
<title>cache: fix misnaming of `git_cache_free`</title>
<updated>2019-02-21T12:35:56+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2019-02-20T09:40:06+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=bbdcd45055ca702eb5083ebf0c70f04c15642f78'/>
<id>bbdcd45055ca702eb5083ebf0c70f04c15642f78</id>
<content type='text'>
Functions that free a structure's contents but not the structure
itself shall be named `dispose` in the libgit2 project, but the
function `git_cache_free` does not follow this naming pattern.

Fix this by renaming it to `git_cache_dispose` and adjusting all
callers to make use of the new name.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Functions that free a structure's contents but not the structure
itself shall be named `dispose` in the libgit2 project, but the
function `git_cache_free` does not follow this naming pattern.

Fix this by renaming it to `git_cache_dispose` and adjusting all
callers to make use of the new name.
</pre>
</div>
</content>
</entry>
<entry>
<title>cache: use iteration interface for cache eviction</title>
<updated>2019-02-15T12:16:49+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2018-12-01T09:18:42+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=6a9117f557fed0afe4007c5de5158e0ebd3a187f'/>
<id>6a9117f557fed0afe4007c5de5158e0ebd3a187f</id>
<content type='text'>
To relieve us from memory pressure, we may regularly call `cache_evict_entries`
to remove some entries from it. Unfortunately, our cache does not support a
least-recently-used mode or something similar, which is why we evict entries
completeley at random right now. Thing is, this is only possible due to the map
interfaces exposing the entry indices, and we intend to completely remove those
to decouple map users from map implementations. As soon as that is done, we are
unable to do this random eviction anymore.

Convert this to make use of an iterator for now. Obviously, there is no random
eviction possible like that anymore, but we'll always start by evicting from the
beginning of the map. Due to hashing, one may hope that the selected buckets
will be evicted at least in some way unpredictably. But more likely than not,
this will not be the case. But let's see what happens and if any users complain
about degraded performance. If so, we might come up with a different scheme than
random removal, e.g. by using an LRU cache.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
To relieve us from memory pressure, we may regularly call `cache_evict_entries`
to remove some entries from it. Unfortunately, our cache does not support a
least-recently-used mode or something similar, which is why we evict entries
completeley at random right now. Thing is, this is only possible due to the map
interfaces exposing the entry indices, and we intend to completely remove those
to decouple map users from map implementations. As soon as that is done, we are
unable to do this random eviction anymore.

Convert this to make use of an iterator for now. Obviously, there is no random
eviction possible like that anymore, but we'll always start by evicting from the
beginning of the map. Due to hashing, one may hope that the selected buckets
will be evicted at least in some way unpredictably. But more likely than not,
this will not be the case. But let's see what happens and if any users complain
about degraded performance. If so, we might come up with a different scheme than
random removal, e.g. by using an LRU cache.
</pre>
</div>
</content>
</entry>
<entry>
<title>oidmap: introduce high-level setter for key/value pairs</title>
<updated>2019-02-15T12:16:48+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2019-01-23T09:48:55+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=2e0a304839764236654e73d38fa380b317a3fac1'/>
<id>2e0a304839764236654e73d38fa380b317a3fac1</id>
<content type='text'>
Currently, one would use either `git_oidmap_insert` to insert key/value pairs
into a map or `git_oidmap_put` to insert a key only. These function have
historically been macros, which is why their syntax is kind of weird: instead of
returning an error code directly, they instead have to be passed a pointer to
where the return value shall be stored. This does not match libgit2's common
idiom of directly returning error codes.Furthermore, `git_oidmap_put` is tightly
coupled with implementation details of the map as it exposes the index of
inserted entries.

Introduce a new function `git_oidmap_set`, which takes as parameters the map,
key and value and directly returns an error code. Convert all trivial callers of
`git_oidmap_insert` and `git_oidmap_put` to make use of it.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Currently, one would use either `git_oidmap_insert` to insert key/value pairs
into a map or `git_oidmap_put` to insert a key only. These function have
historically been macros, which is why their syntax is kind of weird: instead of
returning an error code directly, they instead have to be passed a pointer to
where the return value shall be stored. This does not match libgit2's common
idiom of directly returning error codes.Furthermore, `git_oidmap_put` is tightly
coupled with implementation details of the map as it exposes the index of
inserted entries.

Introduce a new function `git_oidmap_set`, which takes as parameters the map,
key and value and directly returns an error code. Convert all trivial callers of
`git_oidmap_insert` and `git_oidmap_put` to make use of it.
</pre>
</div>
</content>
</entry>
<entry>
<title>oidmap: introduce high-level getter for values</title>
<updated>2019-02-15T12:16:48+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2018-12-17T08:01:53+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=9694ef2064be3ecc3f173af296ab091f0498234d'/>
<id>9694ef2064be3ecc3f173af296ab091f0498234d</id>
<content type='text'>
The current way of looking up an entry from a map is tightly coupled with the
map implementation, as one first has to look up the index of the key and then
retrieve the associated value by using the index. As a caller, you usually do
not care about any indices at all, though, so this is more complicated than
really necessary. Furthermore, it invites for errors to happen if the correct
error checking sequence is not being followed.

Introduce a new high-level function `git_oidmap_get` that takes a map and a key
and returns a pointer to the associated value if such a key exists. Otherwise,
a `NULL` pointer is returned. Adjust all callers that can trivially be
converted.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
The current way of looking up an entry from a map is tightly coupled with the
map implementation, as one first has to look up the index of the key and then
retrieve the associated value by using the index. As a caller, you usually do
not care about any indices at all, though, so this is more complicated than
really necessary. Furthermore, it invites for errors to happen if the correct
error checking sequence is not being followed.

Introduce a new high-level function `git_oidmap_get` that takes a map and a key
and returns a pointer to the associated value if such a key exists. Otherwise,
a `NULL` pointer is returned. Adjust all callers that can trivially be
converted.
</pre>
</div>
</content>
</entry>
<entry>
<title>maps: use uniform lifecycle management functions</title>
<updated>2019-02-15T12:16:48+00:00</updated>
<author>
<name>Patrick Steinhardt</name>
<email>ps@pks.im</email>
</author>
<published>2019-01-23T09:42:46+00:00</published>
<link rel='alternate' type='text/html' href='http://91.123.203.49/cgit/delta/libgit2.git/commit/?id=351eeff3b2a666b8ead5302c1130629597438df6'/>
<id>351eeff3b2a666b8ead5302c1130629597438df6</id>
<content type='text'>
Currently, the lifecycle functions for maps (allocation, deallocation, resize)
are not named in a uniform way and do not have a uniform function signature.
Rename the functions to fix that, and stick to libgit2's naming scheme of saying
`git_foo_new`. This results in the following new interface for allocation:

- `int git_&lt;t&gt;map_new(git_&lt;t&gt;map **out)` to allocate a new map, returning an
  error code if we ran out of memory

- `void git_&lt;t&gt;map_free(git_&lt;t&gt;map *map)` to free a map

- `void git_&lt;t&gt;map_clear(git&lt;t&gt;map *map)` to remove all entries from a map

This commit also fixes all existing callers.
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
Currently, the lifecycle functions for maps (allocation, deallocation, resize)
are not named in a uniform way and do not have a uniform function signature.
Rename the functions to fix that, and stick to libgit2's naming scheme of saying
`git_foo_new`. This results in the following new interface for allocation:

- `int git_&lt;t&gt;map_new(git_&lt;t&gt;map **out)` to allocate a new map, returning an
  error code if we ran out of memory

- `void git_&lt;t&gt;map_free(git_&lt;t&gt;map *map)` to free a map

- `void git_&lt;t&gt;map_clear(git&lt;t&gt;map *map)` to remove all entries from a map

This commit also fixes all existing callers.
</pre>
</div>
</content>
</entry>
</feed>
