{"thread":{"id":"51159","subject":"[GSoC] How to protect cached_objects","startedAt":"2019-05-23T16:57:33Z","lastAt":"2019-05-26T02:44:01Z","messageCount":6,"participants":["Matheus Tavares Bernardino","Jeff King","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"376107","messageId":"CAHd-oW40x3-4rye3QeVGix5pfTCoCHmiwg8ddCeq1E6YYongag@mail.gmail.com","threadId":"51159","inReplyTo":null,"subject":"[GSoC] How to protect cached_objects","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-05-23T16:51:47Z","receivedAt":"2019-05-23T16:57:33Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Hi, everyone\n\nAs one of my first tasks in GSoC, I'm looking to protect the global\nstates at sha1-file.c for future parallelizations. Currently, I'm\nanalyzing how to deal with the cached_objects array, which is a small\nset of in-memory objects that read_object_file() is able to return\nalthough they don't really exist on disk. The only current user of\nthis set is git-blame, which adds a fake commit containing\nnon-committed changes.\n\nAs it is now, if we start parallelizing blame, cached_objects won't be\na problem since it is written to only once, at the beginning, and read\nfrom a couple times latter, with no possible race conditions.\n\nBut should we make these operations thread safe for future uses that\ncould involve potential parallel writes and reads too?\n\nIf so, we have two options:\n- Make the array thread local, which would oblige us to replicate data, or\n- Protect it with locks, which could impact the sequential\nperformance. We could have a macro here, to skip looking on\nsingle-threaded use cases. But we don't know, a priori, the number of\nthreads that would want to use the pack access code.\n\nAny thought on this?\n\nThanks,\nMatheus Tavares\n"},{"id":"376143","messageId":"20190524061352.GB25694@sigill.intra.peff.net","threadId":"51159","inReplyTo":"CAHd-oW40x3-4rye3QeVGix5pfTCoCHmiwg8ddCeq1E6YYongag@mail.gmail.com","subject":"Re: [GSoC] How to protect cached_objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-24T06:13:52Z","receivedAt":"2019-05-24T06:13:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 23, 2019 at 01:51:47PM -0300, Matheus Tavares Bernardino wrote:\n\n> As one of my first tasks in GSoC, I'm looking to protect the global\n> states at sha1-file.c for future parallelizations. Currently, I'm\n> analyzing how to deal with the cached_objects array, which is a small\n> set of in-memory objects that read_object_file() is able to return\n> although they don't really exist on disk. The only current user of\n> this set is git-blame, which adds a fake commit containing\n> non-committed changes.\n> \n> As it is now, if we start parallelizing blame, cached_objects won't be\n> a problem since it is written to only once, at the beginning, and read\n> from a couple times latter, with no possible race conditions.\n> \n> But should we make these operations thread safe for future uses that\n> could involve potential parallel writes and reads too?\n> \n> If so, we have two options:\n> - Make the array thread local, which would oblige us to replicate data, or\n> - Protect it with locks, which could impact the sequential\n> performance. We could have a macro here, to skip looking on\n> single-threaded use cases. But we don't know, a priori, the number of\n> threads that would want to use the pack access code.\n\nIt seems like a lot of the sha1-reading code is 99% read-only, but very\noccasionally will require a write (e.g., refreshing the packed_git list\nwhen we fail a lookup, or manipulating the set of cached mmap windows).\n\nI think pthreads has read/write locks, where many readers can hold the\nlock simultaneously but a writer blocks readers (and other writers).\nThen in the common case we'd only pay the price to take the lock, and\nnot deal with contention. I don't know how expensive it is to take such\na read lock; it's presumably just a few instructions but implies a\nmemory barrier. Maybe it's worth timing?\n\n-Peff\n"},{"id":"376170","messageId":"CACsJy8DFw1Y_bhE=k2ZEMTk+vFvwwmx4GDnRXEQB9cp58M3vLg@mail.gmail.com","threadId":"51159","inReplyTo":"CAHd-oW40x3-4rye3QeVGix5pfTCoCHmiwg8ddCeq1E6YYongag@mail.gmail.com","subject":"Re: [GSoC] How to protect cached_objects","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-05-24T09:55:04Z","receivedAt":"2019-05-24T09:55:33Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino\n wrote:\n>\n\n> Hi, everyone\n>\n> As one of my first tasks in GSoC, I'm looking to protect the global\n> states at sha1-file.c for future parallelizations. Currently, I'm\n> analyzing how to deal with the cached_objects array, which is a small\n> set of in-memory objects that read_object_file() is able to return\n> although they don't really exist on disk. The only current user of\n> this set is git-blame, which adds a fake commit containing\n> non-committed changes.\n>\n> As it is now, if we start parallelizing blame, cached_objects won't be\n> a problem since it is written to only once, at the beginning, and read\n> from a couple times latter, with no possible race conditions.\n>\n> But should we make these operations thread safe for future uses that\n> could involve potential parallel writes and reads too?\n>\n> If so, we have two options:\n> - Make the array thread local, which would oblige us to replicate data, or\n> - Protect it with locks, which could impact the sequential\n> performance. We could have a macro here, to skip looking on\n> single-threaded use cases. But we don't know, a priori, the number of\n> threads that would want to use the pack access code.\n>\n> Any thought on this?\n\nI would go with \"that's the problem of the future me\". I'll go with a\nsimple global (I mean per-object store) mutex. After we have a\ncomplete picture how many locks we need, and can run some tests to see\nthe amount of lock contention we have (or even cache missess if we\nhave so many locks), then we can start thinking of an optimal\nstrategy.\n\nI mean, this is an implementation detail and can't affect object\naccess API right? That gives us some breathing room to change stuff\nwithout preparing for something that we don't need right now (like\nmultiple cached_objects writers)\n\n\n> Thanks,\n> Matheus Tavares\n\n\n\n-- \nDuy\n"},{"id":"376219","messageId":"CAHd-oW4Y6bN+6SCJNEg+w0GMWQcUdiHmTbQfCpJ5J283xU8X+w@mail.gmail.com","threadId":"51159","inReplyTo":"20190524061352.GB25694@sigill.intra.peff.net","subject":"Re: [GSoC] How to protect cached_objects","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-05-25T14:42:58Z","receivedAt":"2019-05-25T14:43:11Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"On Fri, May 24, 2019 at 3:13 AM Jeff King wrote:\n>\n> On Thu, May 23, 2019 at 01:51:47PM -0300, Matheus Tavares Bernardino wrote:\n>\n> > As one of my first tasks in GSoC, I'm looking to protect the global\n> > states at sha1-file.c for future parallelizations. Currently, I'm\n> > analyzing how to deal with the cached_objects array, which is a small\n> > set of in-memory objects that read_object_file() is able to return\n> > although they don't really exist on disk. The only current user of\n> > this set is git-blame, which adds a fake commit containing\n> > non-committed changes.\n> >\n> > As it is now, if we start parallelizing blame, cached_objects won't be\n> > a problem since it is written to only once, at the beginning, and read\n> > from a couple times latter, with no possible race conditions.\n> >\n> > But should we make these operations thread safe for future uses that\n> > could involve potential parallel writes and reads too?\n> >\n> > If so, we have two options:\n> > - Make the array thread local, which would oblige us to replicate data, or\n> > - Protect it with locks, which could impact the sequential\n> > performance. We could have a macro here, to skip looking on\n> > single-threaded use cases. But we don't know, a priori, the number of\n> > threads that would want to use the pack access code.\n>\n> It seems like a lot of the sha1-reading code is 99% read-only, but very\n> occasionally will require a write (e.g., refreshing the packed_git list\n> when we fail a lookup, or manipulating the set of cached mmap windows).\n>\n> I think pthreads has read/write locks, where many readers can hold the\n> lock simultaneously but a writer blocks readers (and other writers).\n> Then in the common case we'd only pay the price to take the lock, and\n> not deal with contention. I don't know how expensive it is to take such\n> a read lock; it's presumably just a few instructions but implies a\n> memory barrier. Maybe it's worth timing?\n\nThe pthread_rwlock_t, right? Nice! I didn't know about this type of\nlock. It will be very handy in other situations as well, thanks for\nthe suggestion.\n\n> -Peff\n"},{"id":"376220","messageId":"CAHd-oW4_u6SMPropxR0tWb2b_Q31n2rda3FKPb9qsnCKwZ=b8Q@mail.gmail.com","threadId":"51159","inReplyTo":"CACsJy8DFw1Y_bhE=k2ZEMTk+vFvwwmx4GDnRXEQB9cp58M3vLg@mail.gmail.com","subject":"Re: [GSoC] How to protect cached_objects","fromName":"Matheus Tavares Bernardino","fromEmail":"matheus.bernardino@usp.br","sentAt":"2019-05-25T16:04:47Z","receivedAt":"2019-05-25T16:07:11Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"On Fri, May 24, 2019 at 6:55 AM Duy Nguyen wrote:\n>\n> On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino\n> wrote:\n> >\n>\n> > Hi, everyone\n> >\n> > As one of my first tasks in GSoC, I'm looking to protect the global\n> > states at sha1-file.c for future parallelizations. Currently, I'm\n> > analyzing how to deal with the cached_objects array, which is a small\n> > set of in-memory objects that read_object_file() is able to return\n> > although they don't really exist on disk. The only current user of\n> > this set is git-blame, which adds a fake commit containing\n> > non-committed changes.\n> >\n> > As it is now, if we start parallelizing blame, cached_objects won't be\n> > a problem since it is written to only once, at the beginning, and read\n> > from a couple times latter, with no possible race conditions.\n> >\n> > But should we make these operations thread safe for future uses that\n> > could involve potential parallel writes and reads too?\n> >\n> > If so, we have two options:\n> > - Make the array thread local, which would oblige us to replicate data, or\n> > - Protect it with locks, which could impact the sequential\n> > performance. We could have a macro here, to skip looking on\n> > single-threaded use cases. But we don't know, a priori, the number of\n> > threads that would want to use the pack access code.\n> >\n> > Any thought on this?\n>\n> I would go with \"that's the problem of the future me\". I'll go with a\n> simple global (I mean per-object store) mutex.\n\nThanks for the help, Duy. What you mean by \"per-object store mutex\" is\nto have a lock for every \"struct raw_object_store\" in the \"struct\nrepository\"? Maybe I didn't quite understand what the \"object store\"\nis, yet.\n\n> After we have a\n> complete picture how many locks we need, and can run some tests to see\n> the amount of lock contention we have (or even cache missess if we\n> have so many locks), then we can start thinking of an optimal\n> strategy.\n\nPlease correct me if I misunderstand your suggestion. The idea is to\nprotect the pack access code at a higher level, measure contentions,\nand then start refining the locks, if needed? I'm asking because I was\ngoing directly to the lower level protections (or thread-safe\nconversions) and planning to build it up. For example, I was working\nthis week to eliminate static variables inside pack access functions.\nDo you think this approach is OK or should I work on a more \"broader\"\nthread-safe conversion first (like a couple wide mutex) and refine it\ndown?\n\n> I mean, this is an implementation detail and can't affect object\n> access API right? That gives us some breathing room to change stuff\n> without preparing for something that we don't need right now (like\n> multiple cached_objects writers)\n\nIndeed, makes sense to leave the multiple writers support to the\nfuture, if it's ever needed. Thanks.\n"},{"id":"376227","messageId":"CACsJy8Aj7EJn9UeC81NnE-_fcLybCzvzqB8rL6T=2oc3Z+RhMA@mail.gmail.com","threadId":"51159","inReplyTo":"CAHd-oW4_u6SMPropxR0tWb2b_Q31n2rda3FKPb9qsnCKwZ=b8Q@mail.gmail.com","subject":"Re: [GSoC] How to protect cached_objects","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-05-26T02:43:32Z","receivedAt":"2019-05-26T02:44:01Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, May 25, 2019 at 11:04 PM Matheus Tavares Bernardino\n wrote:\n>\n> On Fri, May 24, 2019 at 6:55 AM Duy Nguyen wrote:\n> >\n> > On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino\n> > wrote:\n> > >\n> >\n> > > Hi, everyone\n> > >\n> > > As one of my first tasks in GSoC, I'm looking to protect the global\n> > > states at sha1-file.c for future parallelizations. Currently, I'm\n> > > analyzing how to deal with the cached_objects array, which is a small\n> > > set of in-memory objects that read_object_file() is able to return\n> > > although they don't really exist on disk. The only current user of\n> > > this set is git-blame, which adds a fake commit containing\n> > > non-committed changes.\n> > >\n> > > As it is now, if we start parallelizing blame, cached_objects won't be\n> > > a problem since it is written to only once, at the beginning, and read\n> > > from a couple times latter, with no possible race conditions.\n> > >\n> > > But should we make these operations thread safe for future uses that\n> > > could involve potential parallel writes and reads too?\n> > >\n> > > If so, we have two options:\n> > > - Make the array thread local, which would oblige us to replicate data, or\n> > > - Protect it with locks, which could impact the sequential\n> > > performance. We could have a macro here, to skip looking on\n> > > single-threaded use cases. But we don't know, a priori, the number of\n> > > threads that would want to use the pack access code.\n> > >\n> > > Any thought on this?\n> >\n> > I would go with \"that's the problem of the future me\". I'll go with a\n> > simple global (I mean per-object store) mutex.\n>\n> Thanks for the help, Duy. What you mean by \"per-object store mutex\" is\n> to have a lock for every \"struct raw_object_store\" in the \"struct\n> repository\"? Maybe I didn't quite understand what the \"object store\"\n> is, yet.\n\nIt's struct 'raw_object_store'. I think that struct encapsulates all\ndata structures around $GIT_DIR/objects.\n\n> > After we have a\n> > complete picture how many locks we need, and can run some tests to see\n> > the amount of lock contention we have (or even cache missess if we\n> > have so many locks), then we can start thinking of an optimal\n> > strategy.\n>\n> Please correct me if I misunderstand your suggestion. The idea is to\n> protect the pack access code at a higher level, measure contentions,\n> and then start refining the locks, if needed? I'm asking because I was\n> going directly to the lower level protections (or thread-safe\n> conversions) and planning to build it up. For example, I was working\n> this week to eliminate static variables inside pack access functions.\n> Do you think this approach is OK or should I work on a more \"broader\"\n> thread-safe conversion first (like a couple wide mutex) and refine it\n> down?\n\nHaving one or two big locks might be easy to get thread safe, but that\nincreases lock contention and may take forever to fix (it took a long\ntime to kill Linux's \"big kernel lock\", and python's equivalent is\nstill here). So having smaller locks around each shared state makes\nmore sense. At least you will have easier time combining them later if\nyou want (breaking down big locks is much harder).\n\nWhat I was getting at was just stick to simple locks like mutex. Once\nyou have identified all shared states to protect, you can profile to\nhave more information and then decide can to choose a different kind\nof lock, like the read/write one. We might even need to reorganize\ndata structure to be more lock-friendly (or go lockless if you feel\nbrave)...\n-- \nDuy\n"}]}