<div dir="ltr"><div dir="ltr">Hi,<div>It seem I CCed the mailing list accidentally ;-). The git toy is most likely not the easiest toy to start learning C coming from memory managed languages, but the 90MB of dependencies of git give an incredible motivation to do so :-).</div><div><br></div><div>Thank for reviewing read_index(). I will include xmalloc() and check what I am actually pointing to. Read_index is currently a dead and used function. I scaffolded it to get an idea of deserialization in C. It will be more useful once git clone serializes the index correct.</div><div><br></div><div>Regarding the different kind of SHA fields: 1) sha1 field is a dynamic array storing the values of the "git index hash table". I did not invent this. This struct shall represent the actually documented git idx format. The git "hash table" reads the first char of the sha1 hash (FanOutTable(FOT)) and then binary searches the bucket for the requested hash. 2) packsha1 field is the sha1 hash of the pack file which the idx struct/file is created for 3) idxsha1 is the sha1 hash of the overall struct including the packsha1. The last two sha1 field can only be calculated correct, when git clone works correct. So I dont care much about this hashes right now. git uses them most likely to detect bit flips in downloaded backs and calculated indexes. The git pack format V2 is documented here: <a href="https://github.com/git/git/blob/master/Documentation/gitformat-pack.txt#L266">https://github.com/git/git/blob/master/Documentation/gitformat-pack.txt#L266</a> (like was broken due to renamings in the git/git repo. Fixed the links over the weekend.)</div><div><br></div><div>Best regards,</div><div>Moritz</div><div><br></div><div>P.S.: It also corrected git fetch over the weekend, so that I read the actually master head from the remote repo and persists it into HEAD, so that I can get rid of the static version tag hashes in the code.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jan 1, 2023 at 11:01 PM Rob Landley <<a href="mailto:rob@landley.net">rob@landley.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">For context: Moritz is teaching himself C by writing a git implementation for<br>
toybox. I'm kind of impressed. :)<br>
<br>
On 12/29/22 09:09, Moritz Christian Weber wrote:<br>
> Hi Rob,<br>
> I "solved" the issue, which made the git.c code not finding hashes and returned<br>
> NULL (I used a modified/buggy bsearch() instead of the indented bsearchpos()).<br>
> As a result it now clones Toybox 0.0.1 and 0.0.2. bsearchpos() never returns<br>
> NULL, but a long of the position nearest to the hash. The drawback is that it<br>
> can return wrong hashes, if it does not find the intended hash, but the good<br>
> thing is that I can debug the wrong hashes in much better and interpretable way<br>
> in git checkout, if the code does not crash before git checkout.<br>
> <br>
> When cloning toybox 0.0.2, it shows unintended random bytes at the end of the<br>
> recreated source files, which make the files too long. It indicated that the<br>
> delta resolving is not correct yet and will result in wrong hashes. It is also<br>
> confirmed by higher version than 0.0.3.<br>
> <br>
> For version 0.0.3 and higher the git fetch "seems" to work "perfectly", but when<br>
> checking out, some files are interpreted folders. I guess this comes from the<br>
> files with unintended random bytes in the end, which result in wrong hashes,<br>
> which bsearchpos() resolves the next similar hash. The good thing is that I know<br>
> at this level which expected file/hash it was and how it should be resolved.<br>
> Much better starting point to debug delta resolving than if you have to do this<br>
> in fetch while delta resolving. The code feels also much more complete seeing<br>
> how parts of the repository are already checked out.<br>
> <br>
> I started a new email thread and attached you the current version for review.<br>
<br>
I checked the historical versions in to have some history, and did several<br>
simple cleanup passes on it for whitespace and such, and now I'm looking at:<br>
<br>
struct IndexV2 {<br>
...<br>
  char (*sha1)[20];<br>
...<br>
}<br>
<br>
static void read_index(struct IndexV2 *i)<br>
{<br>
  FILE *fpi;<br>
<br>
  i = malloc(sizeof(i));<br>
  i->sha1 = malloc(20*sizeof(char));<br>
<br>
FYI toybox has an xmalloc() wrapper function in lib/xwrap.c that checks for NULL<br>
return from malloc and just aborts with an error if so. (Because it should<br>
basically never happen on a system with an MMU: it means you've run out of<br>
VIRTUAL address space, which really isn't sanely recoverable. The virtual<br>
address space starts out empty (it used to be a repeated copy-on-write mapping<br>
of the zero page, and now it's more complicated but essentially the same thing).<br>
The OS goes in and plugs physical pages into the mapping after the fact as they<br>
get "dirtied" (I.E. written to), and that deferred allocation runs out of memory<br>
the system will swap stuff out, and if the swap partition fills up and the<br>
system actually runs Out Of Memory it invokes the OOM killer which sends the<br>
kill signal to processes to free up memory. Linux people have complained about<br>
the OOM killer for years because it kills their processes and they don't like<br>
it, but if you run without one the system will lock up instead. They've added<br>
buckets of heuristics to try to have ChatGPT levels of stupid pick which process<br>
to kill in OOM situations: there's no right answer, so find it! And as a result,<br>
modern Linux systems spend MUCH longer times swap thrashing before the OOM<br>
killer gives up and lets the system lock up so everything stops you have to<br>
reboot it. This is called progress, apparently. Systemd is adding an OOM killer<br>
subsystem, because of course it is. Systemd is another project like chatgpt to<br>
introduce subtle errors hidden by layers of complexity to prevent anyone from<br>
seeing what specifically is wrong, except instead of descending from technology<br>
to escape beysian spam filtering it's written by a guy who Linus explicitly and<br>
publicly kicked out of linux-kernel, which he almost never does.)<br>
<br>
Yes, I should do a video on that. :)<br>
<br>
Back to the function above: the first malloc is taking the size of the pointer<br>
instead of the size of what it points to, so you're allocating either 4 or 8<br>
bytes instead of whatever IndexV2 adds up to. Which is probably going to<br>
coincidentally work for a bit as you scribble over adjacent memory in the heap<br>
somewhere, but Bad Things will happen at some point.<br>
<br>
But it's the SECOND malloc I'm confused by, because it's sort of halfway to<br>
function pointer syntax but I'm pretty sure that's not what you mean? Do you<br>
want a char **sha1 there perhaps? (You want a pointer to a sized array?) Also,<br>
sizeof(char) is 1 so you don't need to multiply by that...<br>
<br>
What is the sha1 field for? (There's also packsha1 and indexsha1 and I dunno<br>
which is which...)<br>
<br>
Rob<br>
</blockquote></div></div>