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.
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
