Re: [boost] Demangler, summary.

From: Rob Stewart (stewart_at_[hidden])
Date: 2002-09-03 11:28:45

From: Carlo Wood <carlo_at_[hidden]>
> On Fri, Aug 30, 2002 at 01:08:26PM -0400, Rob Stewart wrote:
> > 
> > - Under what scenario will demangle() be invoked from within a
> >   call to malloc()?
> 
> At this moment I am only aware of one case: libcwd.
> In general you could say "memory debuggers" that do demangling
> of function names from which an allocation is performed.
> Output of libcwd can look like:
> 
> MALLOC  : operator new[] (size = 50) = <unfinished>
> BFD     :     address 0x804f95f corresponds to alloctag.cc:50
> MALLOC  : <continued> 0x81c1b38

OK.  So, when demangle() is called, it may be in the middle of a memory
allocation.

> > - Why would the demangle() client care how demangle() manages its
> >   memory?
> 
> Because demangle() uses the STL :/.  I could try to implement

The problem here, then, is that demangle() might cause a recursive call to
malloc() in a naive implementation.  Therefore, you propose providing an
allocator for demangle() to use with its internal STL code, right?  It is also
my understanding that your use of STL containers, for example, is to collect and
cache symbol translations in order to improve performance.  IOW, the alternative
is to do the symbol table lookups on each call to demangle(), and you'd like to
avoid that overhead, right?

Let's start with the assumption that an allocator is needed.  I'm left to wonder
what such an allocator can do.  Someone else just raised the question of what
the memory allocation scheme of that allocator should be?  Is it just a general
purpose function not unlike malloc()?  If so, then the demangle() client will
need to supply OS-specific private heap code in the form of std::allocator to
give you what you need.  That's a pretty tall order for most folks -- perhaps
for you, too.

What if the OS doesn't have private heap functionality?  The only solution there
is for the client to provide a fixed block of memory, reserved from early in the
program run, so there's a good chance that you will get a std::bad_alloc
exception.  If memory is tight enough to make the pre-allocation small enough
not to impinge on the application proper, then changes are good you'll run out
of what you need.  Thus, an unbounded appetite for memory will likely lead to an
exception rather than useful output.

So this leads me to wonder whether it isn't better to curb demangle()'s appetite
for memory.  You could use a circular buffer of cached symbol data to
(hopefully) avoid looking up the same information repeatedly.  The size of that
cache might be a tunable parameter for your library so that memory-constrained
environments might take the performance hit of fewer cache hits resulting from a
small cache, while others might want a realy large cache (thing "nm").

Thus, I don't think an allocator will solve your problem.  Instead, I think
preallocating memory will work better.  Did I miss something in my analysis?

> (For example, I could not store the allocation in an internal
> administration of allocations but immedeately return __libc_malloc,
> however - then when normal user code is using std::allocator and
> at that moment this memory is freed again, the internal administration
> would not find it and assume the user is trying to deallocate an
> invalid pointer).

I didn't follow what you were trying to say there.

> > - If demangle() needs a separate memory scheme, couldn't it use
> >   OS-specific means for establishing a separate heap?  I realize
> >   that implies portability issues, but it would work, wouldn't
> >   it?
> 
> I don't feel that it is worth it.  It's not that much of an issue
> to just pass an Allocator is it?  The only real disadvantage is

Writing an allocator is not for the faint of heart.  It's an unusual world in
which many artifacts of failed or half-successful portability ideas mingle.

> it will turn the demangler code into a template library which could
> cause several different instantiations to run on the same machine
> (as you can't use a template library as a shared library).
> But, since indeed this is probably only used by developers while
> debugging, that is not a real issue in fact.  The second problem

I think Dave Abrahams intends it to be a permanent part of Boost.Python to use
as part of traceback information when things fail.  Thus, it isn't
debugging-only code.  OTOH, Dave is certainly facile enough with the STL,
templates, etc., that I doubt writing an allocator would cause him much pain --
though certainly more than if you write it! ;-)

> of a template library is that is has to be compiled every time
> again (since you need to include it with an #include; well, we

That's certainly a reason to consider viable alternatives, but, given how much
code in Boost is already strictly header-based, that's not a deterrent.

> if only we had precompiled headers :().  However - the developer
> really only needs to add the demangler include in ONE source file,
> and therefore also this is not an issue imho.

What if the call to demangle() is part of some -- dare I say it? -- macro <duck>
that catches exceptions and reports information on the current state of the call
stack or something?

> > - I don't suppose that the information demangle() needs to track
> >   could be preallocated, could it?  (I'm gathering that you want
> >   to track information per symbol, so the data is unbounded.)
> 
> I suppose there is a reasonable limit to what will be needed, but
> you can never garantee that any pre-allocation will really be enough
> unless you preallocate a megabyte.

Or you discard least recently used data.

> >     template <typename Allocator, typename Deallocator>
> >     struct demangler
> >     {
> > 	static std::string type(std::string const & type_i);
> > 	static std::string type(std::type_info const & type_i);
> > 	static std::string symbol(std::string const & symbol_i);
> >     };
> > 
> >   Usage then becomes:
> > 
> >     typedef demangler<?, ?> demangle;
> >     std::cout << demangle::type(mangled_type_name);
> >     std::cout << demangle::type(T.type_id());
> >     std::cout << demangle::symbol(mangled_symbol_name);
> 
> This is still a template library and thus solves nothing.

Actually, I was suggesting that, if you needed the allocator, this interface
might be a good choice.

> But - I like the interface you describe here for passing
> the type of the allocator.

Thanks.

> We could do:
> 
> namespace boost {
> 
>   template <typename Allocator>
>     struct demangler {
>       template <typename InputIterator, typename OutputIterator>
> 	static OutputIterator  type(InputIterator first, InputIterator last, OutputIterator out);
> 	static OutputIterator symbol(InputIterator first, InputIterator last, OutputIterator out);
> 
> 	typedef std::basic_string<char, std::char_traits<char>, Allocator> string;
>     };
> }

I was supposing that you only needed an allocation and deallocation function.
If you're using STL-based code, you'd need to incorporate those into your own
allocator, but it precludes everyone from needing to write an allocator.

> And the usage then will be:
> 
> // Define your own convenient interface:
> std::string demangle_type(std::string const& type_i)
> {
>   std::string out;
>   boost::demangler<std::allocator>::type(type_i.begin(), type_i.end(), out.begin());
>   return out;
> }

In your version, you could default the allocator to std::allocator, and change
"demangler" to "demangle," giving this (with suitable correction to handling
output iterator):

std::string
demangle_type(std::string const & type_i)
{
    std::string result;
    boost::demangle::type(
        type_i.begin(), type_i.end(), std::back_inserter(result));
    return result;
}

-- 
Rob Stewart                           stewart_at_[hidden]
Software Engineer                     http://www.sig.com
Susquehanna International Group, LLP  using std::disclaimer;