On Sun, 4 Sep 2016 00:15:15 +0900 Carsten Haitzler (The Rasterman)
<ras...@rasterman.com> said:

i did a start on this:

https://phab.enlightenment.org/D4275

it was easier than i thought. :) well after i got over some "oopsies" :)

it's a start for discussion purposes

> Why? This directly impacts design and limitations of EO. It also impacts
> performance. It also impacts safety. This is rather important to settle for
> 1.19 as this lays the base for the future of EFL.
> 
> So this past week I was trying to improve EOID lookup and found the EOID
> tables and caches were not locked so if you accessed any object or created or
> deleted objects across 2 or more threads you had race conditions waiting to
> happen. No locks! So I added a spinlock. In the tests there should be zero
> contention so the lock doesn't spin.
> 
> Result? Cost of EOID lookup (to find the real pointer of the object) went from
> 2% to 5% of CPU time. That's how much thread safety costs. It's not cheap.
> This got me thinking. "There has to be another way...".
> 
> So first. What is EOID? This is a 32 or 64bit VALUE we place in a pointer (yes
> I know technically not portable bizarre architectures - We had to do this to
> keep ABI in EFL). This ID gives us an INDIRECT lookup to an object pointer.
> Imagine the simplest version in your head is
> 
> Object *obj  = all_eo_objects[eoid];
> 
> So we take the value and check a table. The object pointer is then either a
> valid ptr (not NULL) and the object is safe to use, or it's NULL (because eo
> maintains the table and ensures any deleted object has it's array member set
> to NULL). It is a little more complex than that. It's fragmented into several
> levels of smaller tables for memory efficiency. Also there's generation counts
> too. In fact check the attached "eoid.png" in this mail for a little bit of a
> better explanation (there are in fact 2 more fields that are used for ref and
> super call detection. ignore them as they are not relevant).
> 
> On 64bit we have a lot of bits to play with. On 32 it's limited. We use 2 bits
> for ref and super, so 30 left. Currently 8 bits for generation count, 5 bits
> for the top table, 5 for the middle table, and last table has 12 bits (so 32
> entries, 32 more than 4096 in the leaf table). Generation count goes up to 255
> before looping to 0 as we always do generation++ every alloc. We might need to
> steal 2 more bits, so i was thinking take one from generation count and one
> from the last table entry value. a bit less safe and lower "max # of objects"
> so on 32bit max 3 objects goes down to 2 million and Generation count to 0 or
> 127. Safety of that part of the check is halved. :(
> 
> So every time you do any call in efl like:
> 
>   efl_gfx_show(obj);
> 
> We HAVE to resolve an EOID to a pointer. This was 2% of CPU time in the
> genlist autobounce test, but now it's 5% thanks to needing to be thread safe.
> This isn't great. We break up the EOID into its various fields, figure out
> what table to access and what row, check for non-NULL pointers, then compare
> generation count so it matches for added safety in case a slot is re-cycled
> (the EOID without generation count is the same between a deleted object and a
> newly created one and we accidentally use the old EOID). Every allocation of
> an eo object makes generation count go up by 1 and we just use the lowest N
> bits as the count, so if the slot is recycled the objects also have to be
> allocated in the same generation (unlikely). On 64bit the above numbers are
> pretty darned big, so there isn't an issue of space. Just on 32bit.
> 
> So the real issue is this lock. Every time and object is looked up, created or
> destroyed we need to lock and unlock all of this EOID table space and related
> caches and generation count etc. It is just a single global lock but it's not
> cheap since we do this SO OFTEN (yes it does have a cache to store the last
> looked-up object, but this is global).
> 
> What can we do? Well remove the lock? Make it cheaper? Well we can't make the
> lock cheaper. I've looked. We MIGHT be able to make it smaller (not relevant
> as there is a single global one), but not cheaper in cycles. More fine grained
> locks won't help because we aren't talking contention here as the issue.
> Literally a SUCCESSFUL lock take and then release with no contention takes 3%
> of our CPU time.
> 
> So here is an idea. I checked. A TLS lookup for any var is 1/5th the cost or
> so of a lock+unlock. We could use __thread and this is FREE (no cost - well
> it's a mov only), but this is only free in binaries not shared libraries, so
> let's talk TLS which is much cheaper than a lock anyway. Why TLS?
> 
> 1. It will drop out cost above a lot.
> 2. We can remove several other locks in EO too cutting some more costs.
> 3. We can REALLY CHEAPLY enforce the rule of "you may not access an object
> outside its owning thread". Because every thread has it's own EOID table, the
> EOID will be local to that thread only. Looking it up in another thread is
> looking up an "invalid" EOID. In fact we can make this pretty much always fail
> by using some domain bits in EOID like i mentioned above (steal some from
> table entries and/or generation count). Now literally stuff will FAIL and not
> magically work 99% of the time if you disobey these rules and access a
> rectangle object or a timer from another thread that doesn't own them as the
> objects literally are not in the local thread EOID table. The tread cannot see
> them (well is very unlikely to see them).
> 
> So how to do this?
> 
> 0. Move the EOID table, and associated data into a TLS structure
> 1. Every thread HAS to do an eo_thread_init() (eo_init can do this implicitly
> for the mainloop thread, and we can make ecore_thread/later Efl.Thread do this
> per thread it creates for you so you don't have to).
> 2. This thread init sets up an initial generation count at a random value so
> generation counts can't easily be in sync and maybe swizzles the order EOID's
> are found/allocated and so on to minimize ID "sameness".
> 3. We take 2 more bits as a thread domain for the EOID. Mainloop thread has
> domain 0. All other threads have domain 1 UNLESS they explicitly ask for a
> "alternate" domain and must do so before any eo objects are created and we
> have domain 3 and 4 for this for "special" domains.
> 4. We make it a clear rule that threads cannot access objects outside of those
> that they created UNLESS:
> 4.1 An object is explicitly SENT from one thread to another (we can do this
> later but if this is done, the object must have a refcount of 1 only, no
> parent, no children, no objects referenced in keys, weak refts to/from this
> object etc.). We can release the EOID entry in thread 1, but not call
> destructor and free object memory, send the POINTER to thread 2, and here a
> new EOID local to that thread is allocated and that pointer adopted.
> 4.2 A whole thread is blocked and its table adopted as a secondary table. This
> is needed for ecore_main_loop_begin/end(). This is safe because the OWNING
> thread is paused during this time. To do this the 2 threads must NOT SHARE the
> same domain. So a regular thread (domain 1) can always do a begin/end on the
> mainloop as they have differing domains. You have 2 more domains to use as
> object brokers that are less likely to have latency like the mainloop.
> 5. As long as we get the ptr of the TLS in the owning thread it will work when
> sent to another thread, so the above sharing of 2 thread tables temporarily
> can be done.
> 7. It's an EO (and EFL)-wide rule that you should not make threadsafe objects
> because EO just won't support it - you have to explicitly send objects around
> or do a begin/end of another thread to look at it's objects (and then that is
> limited to a thread of a different domain - we have 4 so not bad).
> 8. We need to make sure eo doesn't allow you to do things like set a child of
> an object that is in a different domain to the parent, or with weak refs, key
> object refs etc.
> 9. When we do object sending we need maybe pipes with fd's with functions to
> process "incoming objects" and have some kind of eo object with callbacks to
> tell you when it receives a new incoming object so when sent from one thread,
> the thread releases it's EOID but the whole data is floating around UNTIL it
> arrives at the other end and someone needs to know WHEN it arrives and what
> the new EOID is. So we need some kind of per-thread/loop "object receiver"
> and have to glue this into Efl.Loop if there is one in that thread.
> 
> I have most of the nasty bits sorted out ... all but:
> 
> When you are in a begin/end section and you see 2 EOID tables, when you CREATE
> a new object... which one does it go into? Remember that when you CALL a
> method on an obj it may go create objects internally too. How can you
> determine which to use? You should be able to access both without creating
> without issue with domains as above. You could delete fine since an object
> knows which table it belongs to in the current thread context based on domain
> number. They will be different. You can't bind a foreign domain in if it
> matches yours - it'll fail. But creation is special.
> 
> One option... if you create WITH a parent passed, the child must go into the
> same domain automatically. Operations mixing domains in an object tree should
> fail. What about other cases? Create a bare object with no parent... you add
> as a child later. How to choose which domain it goes into? Local or fireign?
> Maybe there is a context you can switch that is in your TLS that tells you
> which to use (local or foreign table). If we have a push/pop setup it'd be
> nice, but it's easy to get wrong. An explicit call to crate with foreign and
> eo_add is local? So eo_foregin_add() uses the foreign domain (if adopted at
> the time, and if not it will either fail or just use local domain then). Worth
> thinking about.
> 
> This buys us REALLY NICE "thread safety" in the way that objects are just not
> allowed to span threads. They must be explicitly sent over and thus ownership
> (and EOID value) changes, or you must explicitly do a begin/end on another
> thread and adopt it's ID table into your local space as a "foregin" table that
> allows you definitely "read only" access easily, even the ability to modify
> and delete, but just creation is tricky. This really will clear up lots of
> mistakes we have been seeing from code that uses threads and does "bad
> things" that happen to work 99% of the time then fail oddly 1% of the time.
> We don't have to write "is this my thread" checking code in every method
> because the design will do that mostly for us as a side-effect of TLS and
> normal EOID checking. This also buys us simplicity when dealing with objects
> as we can assume the nice old fashioned way of "no need to lock or consider
> threads - it will not be an issue", and it buys us a good speedup vs what we
> have now. It does mean another bit of a re-jigging of eo internals and we
> need to add some API's to be able to do begin/end etc. and we can later add
> object sending.
> 
> I'm rather happy with this kind of direction. We never have to make eo objects
> thread safe or create a special eo thread safe base class. Ever. You want to
> talk from thread to thread, then we can have endpoint objects that get created
> with one object on one end of the msg pipe (like a socketpair() or pipe()),
> and a different object on the other end (create in one place then send one
> end to another thread? The object internals hook them up via pipes or
> threadqueues?). This makes currently "incorrect and dangerous code" fail
> early instead of 1% of the time. It catches issues fast. It gets us speedups.
> This potentially impacts promises too, but probably in a good way. This also
> affects bindings - looking at JS/Lua specificially. If Lua had a threading
> model right now it'd be to have 1 luastate per thread, but this means we
> can't share objects... this means eo's model is the same and you would have
> to detach an object from one thread (luastate) and make one appear on the
> other end. I'm also happy that I think this solves a disagreement on how to
> do threading. I know we have to somehow and not just stick our heads in the
> sand. This solves it. It gives a clear optimal model that is relatively
> robust and efficient.
> 
> I can see benefits for memory allocation too. Specifically memory directly
> needed for objects. We can add our own allocators for this instead of using
> libc and these allocators DO NOT need to be threadsafe thus gaining speed
> (well catch - if you send an object across we have to somehow deal with
> this... unknown at the moment - an issue to consider)?
> 
> The downsides are the extra work, the need to add API's to init eo per thread,
> need to check for objects on thread shutdown (need the TLS free func to do
> sanity checking for still-alive objects), the need to add all this foreign vs.
> local table stuff for begin+end and then to hook that in, and the likely need
> to add at least object sending, and the messaging infra. Also it will use a
> bit more memory if you use eo across threads and actually create objects in
> other threads. As well any mempools and other things that we currently share
> across threads may need to become per-thread.
> 
> So ... with that. Questions, comments, queries, devils-advocate. Find issues
> with this. Wrap your head around it. This is very important as this impacts
> many things subtly and some directly and clearly.
> 
> -- 
> ------------- Codito, ergo sum - "I code, therefore I am" --------------
> The Rasterman (Carsten Haitzler)    ras...@rasterman.com
> 


-- 
------------- Codito, ergo sum - "I code, therefore I am" --------------
The Rasterman (Carsten Haitzler)    ras...@rasterman.com


------------------------------------------------------------------------------
_______________________________________________
enlightenment-devel mailing list
enlightenment-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-devel

Reply via email to