On Wed, 24 Apr 2013 16:41:49 +0900 Carsten Haitzler (The Rasterman)
<ras...@rasterman.com> said:
oh.. and i probably should... edit this for.. typos...
> 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
--
------------- 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
