{"thread":{"id":"36370","subject":"Students project on Git (Ensimag)","startedAt":"2014-04-08T15:44:03Z","lastAt":"2014-04-22T10:38:18Z","messageCount":8,"participants":["Matthieu Moy","Michael Haggerty","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"238536","messageId":"vpqr457omgs.fsf@anie.imag.fr","threadId":"36370","inReplyTo":null,"subject":"Students project on Git (Ensimag)","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-04-08T15:44:03Z","receivedAt":"2014-04-08T15:44:03Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Hi,\n\nSince 2010, I'm offering my students in Ensimag\n( http://ensimag.grenoble-inp.fr/ ) to contribute to free software\n(including Git) as part of a school project.\n\nI'm maintaining a list of ideas here:\n\n https://git.wiki.kernel.org/index.php/SmallProjectsIdeas\n\nFeel free to add/improve/comment on these (in this thread or on the\nwiki).\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"239068","messageId":"53512DB6.1070600@alum.mit.edu","threadId":"36370","inReplyTo":"vpqr457omgs.fsf@anie.imag.fr","subject":"Project idea: strbuf allocation modes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-04-18T13:50:46Z","receivedAt":"2014-04-18T13:50:46Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I like that strbuf is getting used more than it used to, and I think\nthat is a good general trend to help git rid of and/or avoid buffer\noverflows and arbitrary limits on strings.\n\nIt is unfortunate that it is currently impossible to use a strbuf\nwithout doing a memory allocation. So code like\n\n void f()\n {\n char path[PATH_MAX];\n\n ...\n }\n\ntypically gets turned into either\n\n void f()\n {\n struct strbuf path;\n\n strbuf_add(&path, ...); <-- does a malloc\n ...\n strbuf_release(&path); <-- does a free\n }\n\nwhich costs extra memory allocations, or\n\n void f()\n {\n static struct strbuf path;\n\n strbuf_add(&path, ...);\n ...\n strbuf_setlen(&path, 0);\n }\n\nwhich, by using a static variable, avoids most of the malloc/free\noverhead, but makes the function unsafe to use recursively or from\nmultiple threads.\n\n\nThe Idea\n========\n\nI would like to see strbuf enhanced to allow it to use memory that it\ndoesn't own (for example, stack-allocated memory), while (optionally)\nallowing it to switch over to using allocated memory if the string grows\npast the size of the pre-allocated buffer.\n\nThe way I envision this, strbuf would gain a flags field with two bits:\n\n STRBUF_OWNS_MEMORY\n\n The memory pointed to by buf is owned by this strbuf. If this\n bit is not set, then the memory should never be freed, and\n (among other things) strbuf_detach() must always call xstrcpy().\n\n STRBUF_FIXED_MEMORY\n\n This strbuf can use the memory of length alloc at buf however\n it likes. But it must never free() or realloc() the memory or\n move the string. Essentially, buf should be treated as a\n constant pointer. If the string overgrows the buffer, die().\n\nThe different bit combinations would have the following effects:\n\n flags == ~STRBUF_OWNS_MEMORY | ~STRBUF_FIXED_MEMORY\n\n The strbuf doesn't own the current memory, but it is allowed to\n grow the buffer into other (allocated) memory. When needed,\n malloc() new memory, copy the old string to the new memory,\n and clear this bit -- but *don't* free the old memory. Note\n that STRBUF_INIT, when buf is initialized to point at\n strbuf_slopbuf, would use this flag setting. This flag\n combination could be used to wrap a stack-allocated buffer\n without preventing the string from growing beyond the\n size of the buffer:\n\n void f()\n {\n char path_buf[PATH_MAX];\n struct strbuf path;\n\n strbuf_wrap_preallocated(&path, path_buf, 0, sizeof(path));\n ...\n strbuf_release(&path);\n }\n\n (Probably the boilerplate could be reduced by using macros.)\n\n flags == STRBUF_OWNS_MEMORY | ~STRBUF_FIXED_MEMORY\n\n This gives the current behavior of a non-empty strbuf.\n\n flags == ~STRBUF_OWNS_MEMORY | STRBUF_FIXED_MEMORY\n\n This would make it possible to use a strbuf to wrap a\n fixed-size buffer that belongs to somebody else and must not\n be moved. For example,\n\n void f(char *path_buf, size_t path_buf_len)\n {\n struct strbuf path;\n\n strbuf_wrap_fixed(&path, path_buf,\n strlen(path_buf), path_buf_len);\n ...\n /*\n * no strbuf_release() required here, but if called it\n * is a NOOP\n */\n }\n\n (Probably the boilerplate could be reduced by using macros.)\n\n It would also be possible to use this mode to dynamically\n allocate a strbuf along with space for its string (i.e., to\n make do with one allocation instead of two):\n\n struct strbuf sb = xmalloc(sizeof(strbuf) + len + 1);\n sb.alloc = len + 1;\n sb.len = len;\n sb.flags = STRBUF_FIXED_MEMORY;\n sb.buf = (void *)sb + sizeof(strbuf);\n *sb.buf = '\\0';\n\n If this is considered useful, it should of course be offered\n via a function.\n\n flags == STRBUF_OWNS_MEMORY | STRBUF_FIXED_MEMORY\n\n This combination seems less useful, but I leave it here for\n completeness. It is basically a strbuf whose length is\n constrained to its currently-allocated size.\n\nThe nice thing is that I believe this new functionality could be\nimplemented without slowing down the most-used strbuf functions. For\nexample, none of the inline functions would have to be changed. The\nflags would only have to be checked when doing memory-related operations\nlike strbuf_grow(), strbuf_detach(), etc.\n\n\nAnyway, I just wanted to get the idea out there. I'd like to get\nfeedback about whether people think this is a good idea. If so, maybe\nI'll add it to the wiki as a suggested project.\n\nI've wanted to work on this myself, but realistically I'm not going to\nhave time in the near future. It might be a good Ensimag project or a\nfuture GSoC project (though it might be a bit \"janitorial\" to excite\nstudents). Improving the strbuf API in this way shouldn't be too\ndifficult, and it can be followed up by an almost limitless number of\nfixes throughout the Git codebase to use the new functionality.\n\nOf course if somebody is looking for a relatively straightforward\nproject, I think this would be a nice improvement: it makes strbufs\neasier and cheaper to use and thereby reduces the temptation to do\nmanual memory management, which is all too prone to creating security\nholes via buffer overflows.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"239074","messageId":"xmqq8ur2d04g.fsf@gitster.dls.corp.google.com","threadId":"36370","inReplyTo":"53512DB6.1070600@alum.mit.edu","subject":"Re: Project idea: strbuf allocation modes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-18T17:21:35Z","receivedAt":"2014-04-18T17:21:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> The Idea\n> ========\n>\n> I would like to see strbuf enhanced to allow it to use memory that it\n> doesn't own (for example, stack-allocated memory), while (optionally)\n> allowing it to switch over to using allocated memory if the string grows\n> past the size of the pre-allocated buffer.\n\nI'd like to see these characteristics, but I would want to see that\nthis is done entirely internally inside the strbuf implementation\nwithout any API impact, other than the initialisation. I do not\nthink the current API contract is too rigid to allow us doing so.\n\n - The API users may peek strbuf.buf in-place until they perform an\n operation that makes it longer (at which point the .buf pointer\n may point at a new piece of memory).\n\n - The API users may strbuf_detach() to obtain a piece of memory\n that belongs to them (at which point the strbuf becomes empty),\n hence needs to be freed by the callers.\n\nAs long as the above two promises are kept intact, it is all\ninternal to the strbuf implementation, current iteration of which\ndoes not have any initial (possibly static) allocation other than\nthe fixed \"terminating NUL\", but your updated one may take a caller\nsupplied piece of memory that is designed to outlive the strbuf\nitself as its initial allocation and the memory ownership can be\nleft as an internal implementation detail to the strbuf without\nbothering the callers.\n"},{"id":"239079","messageId":"5351854E.1080602@alum.mit.edu","threadId":"36370","inReplyTo":"xmqq8ur2d04g.fsf@gitster.dls.corp.google.com","subject":"Re: Project idea: strbuf allocation modes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-04-18T20:04:30Z","receivedAt":"2014-04-18T20:04:30Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/18/2014 07:21 PM, Junio C Hamano wrote:\n> Michael Haggerty writes:\n> \n>> The Idea\n>> ========\n>>\n>> I would like to see strbuf enhanced to allow it to use memory that it\n>> doesn't own (for example, stack-allocated memory), while (optionally)\n>> allowing it to switch over to using allocated memory if the string grows\n>> past the size of the pre-allocated buffer.\n> \n> I'd like to see these characteristics, but I would want to see that\n> this is done entirely internally inside the strbuf implementation\n> without any API impact, other than the initialisation. I do not\n> think the current API contract is too rigid to allow us doing so.\n> \n> - The API users may peek strbuf.buf in-place until they perform an\n> operation that makes it longer (at which point the .buf pointer\n> may point at a new piece of memory).\n> \n> - The API users may strbuf_detach() to obtain a piece of memory\n> that belongs to them (at which point the strbuf becomes empty),\n> hence needs to be freed by the callers.\n> \n> As long as the above two promises are kept intact, it is all\n> internal to the strbuf implementation, current iteration of which\n> does not have any initial (possibly static) allocation other than\n> the fixed \"terminating NUL\", but your updated one may take a caller\n> supplied piece of memory that is designed to outlive the strbuf\n> itself as its initial allocation and the memory ownership can be\n> left as an internal implementation detail to the strbuf without\n> bothering the callers.\n\nI think that's exactly what I described. The only thing that would have\nto change in the strbuf behavior (aside from initialization) is that a\nbuffer-growing operation might die if the string would grow outside of\nthe bounds of the existing buffer when STRBUF_FIXED_MEMORY is set.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"239091","messageId":"xmqq38hab0js.fsf@gitster.dls.corp.google.com","threadId":"36370","inReplyTo":"5351854E.1080602@alum.mit.edu","subject":"Re: Project idea: strbuf allocation modes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-19T00:55:19Z","receivedAt":"2014-04-19T00:55:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> On 04/18/2014 07:21 PM, Junio C Hamano wrote:\n>> Michael Haggerty writes:\n>> \n>>> The Idea\n>>> ========\n>>>\n>>> I would like to see strbuf enhanced to allow it to use memory that it\n>>> doesn't own (for example, stack-allocated memory), while (optionally)\n>>> allowing it to switch over to using allocated memory if the string grows\n>>> past the size of the pre-allocated buffer.\n>> \n>> I'd like to see these characteristics, but I would want to see that\n>> this is done entirely internally inside the strbuf implementation\n>> without any API impact, other than the initialisation. I do not\n>> ...\n>\n> I think that's exactly what I described. The only thing that would have\n> to change in the strbuf behavior (aside from initialization) is that a\n> buffer-growing operation might die if the string would grow outside of\n> the bounds of the existing buffer when STRBUF_FIXED_MEMORY is set.\n\nYup, we are in agreement ;-)\n\nMore seriously, sorry for sounding as if I was objecting. I should\nhave edited s/but/and/ before sending my response out.\n\nThanks.\n"},{"id":"239304","messageId":"vpqr44psuzf.fsf@anie.imag.fr","threadId":"36370","inReplyTo":"53512DB6.1070600@alum.mit.edu","subject":"Re: Project idea: strbuf allocation modes","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-04-22T07:07:16Z","receivedAt":"2014-04-22T07:07:16Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Michael Haggerty writes:\n\n> STRBUF_OWNS_MEMORY\n>\n> The memory pointed to by buf is owned by this strbuf. If this\n> bit is not set, then the memory should never be freed, and\n> (among other things) strbuf_detach() must always call xstrcpy().\n\nI just foresee a small difficulty from the caller side:\n\n char path_buf[PATH_MAX];\n char *detached;\n\n struct strbuf path;\n\n strbuf_wrap_preallocated(&path, path_buf, 0, sizeof(path));\n ...\n detached = strbuf_detach(&path);\n\nthe wrapping/unwrapping of path_buf magically turned a stack-allocated\nbuffer into a heap-allocated one. And the initial goal of avoiding\nmalloc() is defeated. So, essentially, one should avoir using\nstrbuf_wrap_preallocated with strbuf_detach, right? But I agree with\nJunio that if the API is properly used, everything should work. I'm just\nworried that we will add a bit more complexity to the API, and I'm not\nsure we can actually expect noticeable improvements in terms of\nperformance (i.e. do we actually use strbuf for performance-critical\nstuff?).\n\nIn your proposal, would STRBUF_OWNS_MEMORY be a constant, or a flag that\nchange when the internal buffer needs reallocation? My understanding is\nthat it should change (if STRBUF_FIXED_MEMORY is not set), and the\nstrbuf wrapping a preallocated buffer would become a \"normal\" strbuf\nwhen its internal buffer grows.\n\nIf so, your \"strbuf_detach() must always call xstrcpy()\" is to be\nunderstood as \"if STRBUF_OWNS_MEMORY is still set when strbuf_detach()\nis called, then it must always call xstrcpy()\", right?\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"},{"id":"239317","messageId":"535631C0.2020100@alum.mit.edu","threadId":"36370","inReplyTo":"vpqr44psuzf.fsf@anie.imag.fr","subject":"Re: Project idea: strbuf allocation modes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-04-22T09:09:20Z","receivedAt":"2014-04-22T09:09:20Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 04/22/2014 09:07 AM, Matthieu Moy wrote:\n> Michael Haggerty writes:\n> \n>> STRBUF_OWNS_MEMORY\n>>\n>> The memory pointed to by buf is owned by this strbuf. If this\n>> bit is not set, then the memory should never be freed, and\n>> (among other things) strbuf_detach() must always call xstrcpy().\n> \n> I just foresee a small difficulty from the caller side:\n> \n> char path_buf[PATH_MAX];\n> char *detached;\n> \n> struct strbuf path;\n> \n> strbuf_wrap_preallocated(&path, path_buf, 0, sizeof(path));\n> ...\n> detached = strbuf_detach(&path);\n> \n> the wrapping/unwrapping of path_buf magically turned a stack-allocated\n> buffer into a heap-allocated one. And the initial goal of avoiding\n> malloc() is defeated. So, essentially, one should avoir using\n> strbuf_wrap_preallocated with strbuf_detach, right?\n\nCorrect; it wouldn't bring any performance advantages. But\nstrbuf_detach() should be implemented for such strbufs for completeness\nso that after the strbuf is instantiated, users don't have to know its\nallocation mode.\n\n> But I agree with\n> Junio that if the API is properly used, everything should work. I'm just\n> worried that we will add a bit more complexity to the API, and I'm not\n> sure we can actually expect noticeable improvements in terms of\n> performance (i.e. do we actually use strbuf for performance-critical\n> stuff?).\n\nThe whole point of the change is to *allow* strbuf to be used in\nperformance-critical stuff.\n\n> In your proposal, would STRBUF_OWNS_MEMORY be a constant, or a flag that\n> change when the internal buffer needs reallocation? My understanding is\n> that it should change (if STRBUF_FIXED_MEMORY is not set), and the\n> strbuf wrapping a preallocated buffer would become a \"normal\" strbuf\n> when its internal buffer grows.\n\nCorrect. STRBUF_OWNS_MEMORY itself is of course a constant like 0x02 (a\nmask to set/clear a bit in the flags) but the corresponding flags bit\nwould sometimes be changed internal to the strbuf implementation. For\nexample, if the buffer is grown past its original size (when\nSTRBUF_FIXED_MEMORY is not set) the bit would be set.\n\nAfter strbuf_detach(), there would be no automatic way to re-attach such\na strbuf to its original heap-allocated memory. So in this situation\nthe buffer would have to be pointed at strbuf_slopbuf again, and the\nSTRBUF_OWNS_MEMORY bit would be cleared again.\n\n> If so, your \"strbuf_detach() must always call xstrcpy()\" is to be\n> understood as \"if STRBUF_OWNS_MEMORY is still set when strbuf_detach()\n> is called, then it must always call xstrcpy()\", right?\n\nExactly.\n\n\nHow does the size of this project compare to what you are looking for\nfor your Ensimag students?\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"239326","messageId":"vpqa9bdsl7p.fsf@anie.imag.fr","threadId":"36370","inReplyTo":"535631C0.2020100@alum.mit.edu","subject":"Re: Project idea: strbuf allocation modes","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@grenoble-inp.fr","sentAt":"2014-04-22T10:38:18Z","receivedAt":"2014-04-22T10:38:18Z","isPatch":false,"sender":{"key":"matthieu.moy@grenoble-inp.fr","avatar":"https://gravatar.com/avatar/72c8a2705971a25dfaff23cece15130d405685845d911aedd5667ace277f3fc5?d=mp&s=160"},"body":"Michael Haggerty writes:\n\n> On 04/22/2014 09:07 AM, Matthieu Moy wrote:\n>\n> The whole point of the change is to *allow* strbuf to be used in\n> performance-critical stuff.\n\nOK. It should not make the current use of strbuf any harder anyway.\n\n>> In your proposal, would STRBUF_OWNS_MEMORY be a constant, or a flag that\n>> change when the internal buffer needs reallocation? My understanding is\n>> that it should change (if STRBUF_FIXED_MEMORY is not set), and the\n>> strbuf wrapping a preallocated buffer would become a \"normal\" strbuf\n>> when its internal buffer grows.\n>\n> Correct. STRBUF_OWNS_MEMORY itself is of course a constant like 0x02\n\nYes, I meant \"the STRBUF_OWNS_MEMORY flag\".\n\n> How does the size of this project compare to what you are looking for\n> for your Ensimag students?\n\nI do not yet have applications for this project (it should come within\nthe next few days). It greatly depends on students and team size. I\nalways start with a \"warm up patch\" (like GSoC's microprojects), and\ndepending on the time taken for it, I direct students to bigger or\nsmaller projects.\n\nYour proposal is a bit tricky (it requires a good understanding of C and\nmemory management), but it is a purely local change (i.e. you can take\nstrbuf.[cf] out of Git's source code and hack it as a ~500 LOC project,\nunit-test and document the result in a self-contained way), so it should\nbe doable. Using the new API features here and there in Git's source\ncode is another story though.\n\nI've added the proposal with a link to this discussion here:\n\n https://git.wiki.kernel.org/index.php/SmallProjectsIdeas#Allow_finer_memory_management_in_the_strbuf_API\n\n-- \nMatthieu Moy\nhttp://www-verimag.imag.fr/~moy/\n"}]}