On Wed, 24 Apr 2013 16:19:50 +0900 Carsten Haitzler (The Rasterman)
<ras...@rasterman.com> said:
> On Wed, 24 Apr 2013 08:27:01 +0300 "daniel.za...@samsung.com"
> <daniel.za...@samsung.com> said:
>
> > Hi Jeremy,
> >
> > On 04/24/2013 12:00 AM, Jérémy Zurcher wrote:
> > > Hi,
> > > I did enjoy it!
> > > even if I'wd prefered a pointer then ID_TABLE macro,
> > > just a matter of taste I suppose ;)
> > I did it because it was too much with the
> > _eo_ids_tables[table_id][int_table_id], I mean not readable. But I am
> > sure it can be written better ;-)
> > >
> > > a question,
> > > what did you based your 32 and 64 bits decomposition on?
> > > equations, benchmarks, moon's CxA ?
> > no equations.
> > Well let's say that for the moment, it is not enough optimized. The most
> > important was to not have big internal tables and to have enough bits
> > for the generation to be efficient.
> > For 64 bits, well, hum, I don't know what I thought to put 20 bits for a
> > table size. Raster already spanked me for that ;-)
> >
> > Concerning optimization, in 32 bits, I think we could increase the
> > generation #bits and reduce the tables #bits because we will never reach
> > 4M of objects. I never saw more than 5K objects. So we could steal 2
> > bits from there (we would have max. 1M objects) for the generation and
> > so increase the stability.
>
> really? no more than 5k objects? interesting. i was maybe expecting 20-40k.
> and yes - i did have to spank a bit on the table sizes on 64bit. i adjusted
> things so we use 30bits for generation counter on 64bit and thus 34bits for
> obj id. since the code splits object lookup into a 3 level table (master
> table array, inter table and then child table),i allocated 11 bits for master
> and inter tables and 12 for child table. this means our "base cost" for our
> first 4k objects is 16k+16k+65k. for every extra 4k object we spend another
> 65k.
>
> now slight catch... i ALSO changed the table allocation to use mmap() of
> anonymous memory. why? separate memory regions for storign the table away from
> memory managed by libc (malloc etc.). this means the "chance" of someone
> finding the memory areas by ccidentally overrunning an existing allocation
> (walk off the end or beginning of an allocation), OR by accidentally accessing
> a previously freed pointer that has ben recycled... is basically almost 0. to
> talk off the end means they will probably have to walk of a valid memry
> mapping into unmapped space and then segv anyway, so chances of table
> corruption now are very very very small, UNLESS that corruption problem is
> inside eo_id code.
>
> now to the catch... to do this i made it mmap and that means it mmapes in
> units of 4k pages.. so adding in accounting overhead, we actually cost 20k+20k
> +68k for the base and each new set of 4k objects costs another 68k (on
> 64bit). these costs on 32bit are moe like 4k+4k+8k for the first 1024 objects
> and an extra 8k for each 1024 objects. i'm actually thinking i should re-jig
> 32bit.
>
> so we divide the obj id into 3 tables (master.inter.sub):
>
> 32bit: 8.4.10 = 22bits (max 4 million objects) = 4k+4k+8k (first 1024)
> 64bit: 11.11.12 = 34bits (max 16 billion objects) = 20k+20k+68k (first 4096)
>
> i think i should adjust 32bit to be maybe 5.5.12 (this brings our costs to
> 4k+4k+20k for the first 4096 objects, and an extra 20k for the next 4096)...
> since object COUNTs will be the same on 32 and 64bit i think this works well
> as given "no more than 5k" for i guess large complex apps (lets pad this up
> to 8k) we pay the base cost plus an extra leaf table ... on a heavy app (20+20
> +68+68 on 64bit or 4+4+20+20 on 32bit - after rejing (before rejig 4+4+(8*8)
> so we go from 72k to 48k - but if we assume small # of objects we are better
> off adjusting to 6.7.9 so our base cost is 4k+4k+4k for 512 and 4k for each
> 512 which is a lower base cost of 12k and then for 8k objects the same as now
> - 72k).
>
> so the question is.. optimize for 4-8k objects and thus lower our cost for
> that from 72k to 48k... or optimize for small # of objetcs, which means
> adjusting the current setup anyway to 6.7.9... for small object counts our
> base cost goes from 28k to 12k. i think i lean to optimizing for 4-8k
> objects... because over time i suspect we will use eo more and more and make
> more objects... a quick look at counting # of objects daniel is right. i'm
> seeing things like 2-4k for elementary_test (even if i push it) and e17 too
> (with some pushing)... they break the 4k mark after some pushing ... so i
> suspect this will be common enough.
>
> (sorry - lots of thinking out aloud here to give reasoning for wanting to
> change the 32bit obj id allocation division).
>
> so people know... what the obj id vs generation count is... the id is the
> actoual object identifier number. each object has a unique one. it is
> literally its entry in a table (0, 1, 2, 3... N). this table has a fixed
> capacity per architecture (22bits or 4m objects on 32bit, and 34bits or 16b
> objects on 64bit). objects may, in the c api appear to return a pointer, but
> stuffed into this pointer is now the id... and all acess is done by looking
> UP this id in this multi-level table and safely checking the appropriate slot
> in the table has a valid (non-null) pointer finally pointing to an actual
> object struct. every table entry is EITHER null OR valid. it can never be
> non-null and non-valid. on creation of every object it gets a table entry. on
> freeing (deletion) its entry is released and nulled out. at least that is the
> theory ASSUMING all object creation points go through this table path as well
> as deletion paths. if they don't - we have a bug in eo and that must be fixed.
> this also assumes that efl code that has access to the obj ptr itself is "much
> more trusted" than "3rd party code" so efl wont accidentally free this obj
> pointer and thus not go through the deletion path that fixes up the table.
>
> all of this work is a result of observing developer usage of efl over years
> and finding that there is gnerally a problem in "pointer/memory management"
> inside apps and that spills over into efl in the form of accessing invalid
> (deleted) evas objects or deleted timers etc. etc., then using up efl
> developer time hunting down a bug in an application just because a crash
> happens inside some object sanity check (eg magic number checking and the
> magic number is store in the obj struct and if the ptr points to inaccessible
> memory... we segv). this table indirection does add overhead. we know that.
> it is a "necessary evil" to address "application developer concerns" and to
> cut back on time chasing irrelevant bugs. this is WHY eo has this odd eo_do()
> thing that you can pack MULTIPLE methods/operations for a single object into
> the args... it means we pay this table lookup cost only ONCE for several
> method calls - thus ammortising the cost across multiple "old school" method
> and thus hopefully "breaking even" once everything is using this eo api and
> batching methods nicely.
>
> so what are the other 10 or 30 bits in the pointer - now become id handle -
> used for? well it's a sanity check. eveyr time any object is created, a
> gneration counter ticks over. it loops/repeats every N values (1024 on 32bit,
> 1billion or so on 64bit). this generation count is no part of the id entry in
> he table but it IS packed into the pointer returned and so when we do a lookup
> we strip off the generation count (10 or 30 bits) and then use the id section
> to do the lookup we then COMPARE the generation count ALSO stored in the table
> next to the entry to the generation count we stripped out. i they do not
> match... it is an invalid access. why? we are recycling a table entry. likely
> an object was deleted, table entry freed, then recycled, and we try access
> again with an old handle frm the outside. it *IS* possible, in theory, for the
> generation count to accidentally match (1 in 1024 chance on 32bit and 1 in a
> billion chance on 64bit). then the object dereference goes through and our
> code calls methods on perhaps the wrong object. this would happen if malloc
> recycled a pointer address too, so we are no worse off really. we STILL check
> on object class types (ie the method id has to exist for that object class
> and since method ides are unique globally and not class-relative) we still
> have a lot of safety here. no crashing inside efl still, but maybe
> misbehaviour... but our CHANCES of this should have been drastically
> reduced... ESPECIALLY on 64bit architectures. rememebr this applies ONLY to
> invalid object references that ALSO have been recycled AND whose generation
> id match.
>
> now... we still hve a few things to do here to make safety even more robust.
>
> 1. don't recycle id's so aggressively. have a "zombie pool" of id's with a
> high and low watermark. this means an object id is not going to be recycled
> "soon" and thus he most common accesses like del() then use() a few lines
> later or while walking back up the stack to parent callers, are caught as the
> id itself simply is forcibly invalud (nulled out) and remains so for a while
> as its in the zombie trash pool. maybe have 1024 or 2048 zombie entries.
>
> 2. obj ptr and gneration cunt are in 2 separate arrays - thus not continuous
> in memory. ue to cacheline fetches these should be merged so they are
> adjacent so we pay only 1 cacheline fetch delay if not already in cache
> instead of 2.
>
> 3. checksum each table row. we consunme 1 void * size for the pointer in each
> row AND 1 void * for the generation count. even if gneration count is only
> 10bit or 30bit, due to alignment and doing #2 above we will spend a void * for
> alignment reasons. we SHOULD pack a checksum into the generation count
> region. if a table entry should now be struct { void *ptr; unitptr_t
> checksum:22; unitptr_t generation:10; } or... similar for 64bit. this checksum
> should just be a ead simple checksum of pointer+generation count elements
> (maybe a simple xor or so) to try detect if perhaps someone did accidentally
> find out table and scribble over parts of it. we chould compare checksum on
> each access and generate it on each write to that table row. this doesn't help
> with our master and inter table though which are just raw pointers... no
> generation count in there. perhaps we should checksum all the pointers in each
> of these tables too... or checksum sections/ranges. this might be lean enough
> to ship with production releases, BUT... might not be... we have to see, but
> it is an option for debug releases (during development) for sanity checks.
>
> 4. since we forcibly took control over our table allocation... and it is
> always a multiple of pages... we can use mprotect to remove write access
> UNLESS eo_id is modifying that table. this is expensive as every change has
> to go into kernel space and change pagetable information, so it wouln't be
> something we do in production release code, BUT debug code could definitely
> enable this as a way of catching table corruption instantly via a segv. :)
>
> 5. we currently nver free tables once they are empty. we just keep a bunch of
> empty tables arund to be re-used. we need to of course keep a zombie table
> pool around of maybe a few tables.. again - high/low watermark, and then
> release when we ee we are not going to re-use our spare tables any time soon.
> given current object counts in things like elementary_test and enlightenmnt,
> we at most will find ourselves with only 1 spare empty leafe table at the
> moment... so this is not high priority.
oh... 6. the trash queue is managed by eina.. in malloced memory - this needs
to move into probably fixed size buffers inside the table leaf struct so this
only lives in custom mmaped memory owned by eo_id.
>
> someone... should... blog... about... this... :) i have to say.. the eo id
> thing is rather cool and unique... you don't see this kind of thing many
> places in c or c++ toolkits like efl (or gtk+ or qt) and it really can hlp
> with robustness a LOT. this is all part of some major groundwork overhauling
> these guys in israel have done and i have to say... it has been done very
> well, considering how deep in the stack this lives and how many things it
> affects (not just eo_id but eo in general). so kudos to the team!
>
> > >
> > > regards
> > > Jérémy
> > >
> > >
> > > On Tuesday 23 April 2013 09:59, daniel.za...@samsung.com wrote :
> > >> Hi all,
> > >>
> > >> This morning, I pushed the Eo pointers indirection feature. As I wrote
> > >> in the log, it is not API break. It will help us against bad usage of Eo
> > >> objects pointers, e.g access an object that has already been deleted...
> > >> So if you see that the Eo* that you receive from eo_add doesn't seem
> > >> like a "normal" pointer, but like 0x1000401, just know it is normal. If
> > >> you need a better explanation on the mechanism used, check the file
> > >> eo_ptr_indirection.c in src/lib/eo.
> > >>
> > >> If you see error messages "obj_id ... is not pointing to a valid object.
> > >> Maybe it has already been freed.", check your Eo objects or contact me.
> > >>
> > >> Enjoy
> > >> JackDanielZ
> > >>
> > >> ------------------------------------------------------------------------------
> > >> Try New Relic Now & We'll Send You this Cool Shirt
> > >> New Relic is the only SaaS-based application performance monitoring
> > >> service that delivers powerful full stack analytics. Optimize and
> > >> monitor your browser, app, & servers with just a few lines of code. Try
> > >> New Relic and get this awesome Nerd Life shirt!
> > >> http://p.sf.net/sfu/newrelic_d2d_apr
> > >> _______________________________________________ enlightenment-devel
> > >> mailing list enlightenment-devel@lists.sourceforge.net
> > >> https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
> > >
> > > ------------------------------------------------------------------------------
> > > Try New Relic Now & We'll Send You this Cool Shirt
> > > New Relic is the only SaaS-based application performance monitoring
> > > service that delivers powerful full stack analytics. Optimize and monitor
> > > your browser, app, & servers with just a few lines of code. Try New Relic
> > > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> > > _______________________________________________
> > > enlightenment-devel mailing list
> > > enlightenment-devel@lists.sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
> >
> >
> >
> > ------------------------------------------------------------------------------
> > Try New Relic Now & We'll Send You this Cool Shirt
> > New Relic is the only SaaS-based application performance monitoring service
> > that delivers powerful full stack analytics. Optimize and monitor your
> > browser, app, & servers with just a few lines of code. Try New Relic
> > and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> > _______________________________________________
> > enlightenment-devel mailing list
> > enlightenment-devel@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
>
>
> --
> ------------- Codito, ergo sum - "I code, therefore I am" --------------
> The Rasterman (Carsten Haitzler) ras...@rasterman.com
>
>
> ------------------------------------------------------------------------------
> Try New Relic Now & We'll Send You this Cool Shirt
> New Relic is the only SaaS-based application performance monitoring service
> that delivers powerful full stack analytics. Optimize and monitor your
> browser, app, & servers with just a few lines of code. Try New Relic
> and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
> _______________________________________________
> enlightenment-devel mailing list
> enlightenment-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
--
------------- Codito, ergo sum - "I code, therefore I am" --------------
The Rasterman (Carsten Haitzler) ras...@rasterman.com
------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
_______________________________________________
enlightenment-devel mailing list
enlightenment-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/enlightenment-devel
