shared_ptr implementation

[bitrex]

I wrote a little memory pool allocator implementation that I hope to use
with a couple embedded projects that use processors without an MMU:
Cortex M4, etc.

It's working pretty well with the STL containers like std::vector, but
I'd like to have the ability to return managed standalone pointers to
the objects in the pool that automatically de-allocate the objects when
they go out of scope.

I've read that correct implementation of smart pointers is a difficult
thing for a C++ newbie to get right. I've looked over the code for
std::unique_ptr and std::shared_ptr in the STL for C++11, and indeed
they appear fairly complex, with a lot of excess #ifdefs for conditional
compilation for architecture features that don't seem to be really
relevant for my application.

I'm wondering if anyone could provide a reference for an example
implementation of smart pointers that are known to be semantically
correct, but would be more suitable for my narrow application.

[bitrex]

This policy based implementation looks like a good starting point:

http://axter.com/smartptr/classsmart__ptr.htm

[Paavo Helde]

On 14.12.2016 19:13, bitrex wrote:
> I wrote a little memory pool allocator implementation that I hope to use
> with a couple embedded projects that use processors without an MMU:
> Cortex M4, etc.
>
> It's working pretty well with the STL containers like std::vector, but
> I'd like to have the ability to return managed standalone pointers to
> the objects in the pool that automatically de-allocate the objects when
> they go out of scope.
>
> I've read that correct implementation of smart pointers is a difficult
> thing for a C++ newbie to get right. I've looked over the code for
> std::unique_ptr and std::shared_ptr in the STL for C++11, and indeed
> they appear fairly complex, with a lot of excess #ifdefs for conditional
> compilation for architecture features that don't seem to be really
> relevant for my application.

If you can use STL in your project, then it looks like you are finished.
Just use std::allocate_shared(your_allocator(), ...) for creating your
objects.

> I'm wondering if anyone could provide a reference for an example
> implementation of smart pointers that are known to be semantically
> correct, but would be more suitable for my narrow application.

If you need to create a new smartpointer class from scratch, then this
is not so hard (certainly simpler than creating a threaded binary tree,
discussed else-thread).

Do you need weak pointers? Do you need thread-safe refcounting? Do you
need const-correctness? Do you need automatic conversions from derived
class smartpointers to base class smartpointers? Do you need to support
any other classes than your own?

If answer to all of these questions is no, then the smart pointer class
becomes pretty trivial. You can use "internal reference counting",
meaning that the reference counter is placed directly inside your
objects (in a common base class). This makes things a bit simpler. The
smartpointer class itself is straightforward, one just needs to take
care to define *all* needed operations and get the self-assignment and
cycle breaking assignments correct.

Example:

#include <cstddef>

// Base class for refcounted objects.
class RefCountedBase {
int refcount_;
public:
RefCountedBase(): refcount_(0) {}
RefCountedBase(const RefCountedBase& b): refcount_(0) {}
RefCountedBase& operator=(const RefCountedBase& b) { return *this; }
RefCountedBase& operator=(RefCountedBase&& b) { return *this; }
virtual ~RefCountedBase() {}
void Capture() {
++refcount_;
}
void Release() {
if (--refcount_==0) {
// destroy the object
delete this;
}
}
};

template<typename T>
class SmartPointer {
T* p_;
public:
SmartPointer(): p_(nullptr) {}
SmartPointer(std::nullptr_t): p_(nullptr) {}
explicit SmartPointer(const T* p): p_(const_cast<T*>(p)) {
if (p_) {
p_->Capture();
}
}
SmartPointer(const SmartPointer& b): p_(b.p_) {
if (p_) {
p_->Capture();
}
}
SmartPointer(SmartPointer&& b): p_(b.p_) {
b.p_ = nullptr;
}
~SmartPointer() {
if (p_) {
p_->Release();
}
}
const SmartPointer& operator=(const SmartPointer& b) {
// Support self assignment
if (b.p_) {
b.p_->Capture();
}
// Support cycle breaking
T* q = p_;
p_ = b.p_;
if (q) {
q->Release();
}
return *this;
}
const SmartPointer& operator=(SmartPointer&& b) {
// Detect self assignment
if (p_!=b.p_) {
// Support cycle breaking
T* q = p_;
p_ = b.p_;
b.p_ = nullptr;
if (q) {
q->Release();
}
}
return *this;
}
T& operator*() const {
return *p_;
}
T* operator->() const {
return p_;
}
T* get() const {
return p_;
}
bool operator<(const SmartPointer& b) const {
return p_<b.p_;
}
explicit operator bool() const { return p_!=nullptr; }
};

class A;
typedef SmartPointer<A> APtr;

class A: public RefCountedBase {
};

#include <vector>
int main() {
APtr a1(new A());
std::vector<APtr> test1(100, a1);
test1.push_back(APtr(new A()));
test1.push_back(APtr(new A()));
a1 = nullptr;
test1.clear();
// all A-s now deleted, however many there were.
}

[bitrex]

On 12/15/2016 09:36 AM, Paavo Helde wrote:
> On 14.12.2016 19:13, bitrex wrote:
>> I wrote a little memory pool allocator implementation that I hope to use
>> with a couple embedded projects that use processors without an MMU:
>> Cortex M4, etc.
>>
>> It's working pretty well with the STL containers like std::vector, but
>> I'd like to have the ability to return managed standalone pointers to
>> the objects in the pool that automatically de-allocate the objects when
>> they go out of scope.
>>
>> I've read that correct implementation of smart pointers is a difficult
>> thing for a C++ newbie to get right. I've looked over the code for
>> std::unique_ptr and std::shared_ptr in the STL for C++11, and indeed
>> they appear fairly complex, with a lot of excess #ifdefs for conditional
>> compilation for architecture features that don't seem to be really
>> relevant for my application.
>
> If you can use STL in your project, then it looks like you are finished.
> Just use std::allocate_shared(your_allocator(), ...) for creating your
> objects.

On an ARM this may be possible. If I wanted to use this pool on
something like a high-end AVR 8 bit it wouldn't be, as unfortunately the
STL that is available for that platform is not entirely C++11 compatible
or complete (it just doesn't have the horsepower for many STL
structures, anyway.)

Containers like std::vector seem to perform admirably on a "modern" 8
bit architecture, but something like std::map I would be more cautious
about.

The C++11 STL smart pointers are out, as I guess they assume nobody
would be using them on an architecture with no MMU, where you shouldn't
really be dynamically allocating objects in raw form to the heap.

>> I'm wondering if anyone could provide a reference for an example
>> implementation of smart pointers that are known to be semantically
>> correct, but would be more suitable for my narrow application.
>
> If you need to create a new smartpointer class from scratch, then this
> is not so hard (certainly simpler than creating a threaded binary tree,
> discussed else-thread).
>
> Do you need weak pointers? Do you need thread-safe refcounting? Do you
> need const-correctness? Do you need automatic conversions from derived
> class smartpointers to base class smartpointers? Do you need to support
> any other classes than your own?
>
> If answer to all of these questions is no, then the smart pointer class
> becomes pretty trivial. You can use "internal reference counting",
> meaning that the reference counter is placed directly inside your
> objects (in a common base class). This makes things a bit simpler. The
> smartpointer class itself is straightforward, one just needs to take
> care to define *all* needed operations and get the self-assignment and
> cycle breaking assignments correct.

Thanks so much! AFAIK right now, for my intended application the answers
to those questions is no, except I'm not entirely sure about thread-safe
reference counting. I'm hoping to use the code in a message queue for an
event-driven real time system, sort of like the "observer pattern": one
object needs to pass a message with some data to another, so it
instantiates a data package in its pool, plops a reference to the
package in a shared queue (like a vector of smart pointers), the
intended receiver listens for it, consumes the data, pops the reference
off the queue and everything is cleaned up.

I've taken some stabs at doing this using "straight C++", like using
abstract classes which all the message packages inherit from and
polymorphism, but it's seemed difficult to implement this type of system
cleanly and extensibly (and without a lot of vtable overhead) without
some fashion of dynamic memory allocation and smart pointer which can
handle generic types.

So there will likely be threads of a fashion, but it will be more in the
vein of a cooperative multitasking/round robin scheduler "protothreads"
type situation than full-fledged threads where there's context-switching
and the entire register set and state is stored in a stack frame.

[Paavo Helde]

On 15.12.2016 17:25, bitrex wrote:
> to those questions is no, except I'm not entirely sure about thread-safe
> reference counting.

Making this schema thread-safe is pretty simple, in C++11 one just needs
to declare the refcounter as std::atomic<int> instead of int.
Alternatively, I imagine that there might be some read-and-update atomic
operations present also on embedded platforms. One only needs to
increment and decrement the refcounter atomically and detect when it
drops to zero.

Cheers
Paavo

[bitrex]

Thanks. Often on small uPs simply disabling interrupts (assuming that a
timer interrupt is where the scheduler "tick" is coming from) and
re-enabling after read/write is enough to ensure the operation is atomic.

[Jorgen Grahn]

On Thu, 2016-12-15, bitrex wrote:
...

> The C++11 STL smart pointers are out, as I guess they assume nobody
> would be using them on an architecture with no MMU, where you shouldn't
> really be dynamically allocating objects in raw form to the heap.

I was happily using dynamic allocation on such systems in the early
1990s. So was anyone else programming e.g. the Commodore-Amiga. An
MMU is not a requirement for malloc/new.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Alf P. Steinbach]

On 15.12.2016 21:39, Jorgen Grahn wrote:
> On Thu, 2016-12-15, bitrex wrote:
> ...
>> The C++11 STL smart pointers are out, as I guess they assume nobody
>> would be using them on an architecture with no MMU, where you shouldn't
>> really be dynamically allocating objects in raw form to the heap.
>
> I was happily using dynamic allocation on such systems in the early
> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
> MMU is not a requirement for malloc/new.

As I recall the original Amiga used an MC68000 processor, with a 24-bit
address bus and MMU?

The 68000 was very nice.

:)


Cheers!,

- Alf

[Scott Lurndal]

IIRC, 68030 was the first 68k with an integrated MMU. Even the
88100 needed an 88200 for the MMU functionality.

The Amiga 1000 (sold mine recently) had a 7mhz 68000.

[bitrex]

On 12/15/2016 03:39 PM, Jorgen Grahn wrote:
> On Thu, 2016-12-15, bitrex wrote:
> ...
>> The C++11 STL smart pointers are out, as I guess they assume nobody
>> would be using them on an architecture with no MMU, where you shouldn't
>> really be dynamically allocating objects in raw form to the heap.
>
> I was happily using dynamic allocation on such systems in the early
> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
> MMU is not a requirement for malloc/new.
>
> /Jorgen
>

Sure, new works just fine with the Arduino/AVR environment, etc. For
example if you want to have some object ready to use on main loop start
you can do:

#include <stdint.h>
#include <new>

struct MyObject {
void do_stuff() { etc.. }
};

MyObject* my_object1 = nullptr;
MyObject* my_object2 = nullptr;

static uint8_t my_object_buf[sizeof(MyObject)];
static uint8_t *const buf_ptr = &my_object_buf[0];

void setup() {
//someplace in heap determined by compiler
my_object1 = new MyObject();

//placed in static buffer
my_object2 = new (buf_ptr) MyObject();
}

void loop() {
my_object1->do_stuff();
my_object2->do_stuff();
}

I can delete and new objects from and into buf_ptr as much as I want
with no problems if they're of type MyObject. But I don't think using
"raw" new and delete as with my_object1 would be a good idea over and
over again from a fragmentation standpoint...

[David Brown]

On 15/12/16 22:29, bitrex wrote:
> On 12/15/2016 03:39 PM, Jorgen Grahn wrote:
>> On Thu, 2016-12-15, bitrex wrote:
>> ...
>>> The C++11 STL smart pointers are out, as I guess they assume nobody
>>> would be using them on an architecture with no MMU, where you shouldn't
>>> really be dynamically allocating objects in raw form to the heap.
>>
>> I was happily using dynamic allocation on such systems in the early
>> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
>> MMU is not a requirement for malloc/new.
>>
>> /Jorgen
>>

> I can delete and new objects from and into buf_ptr as much as I want
> with no problems if they're of type MyObject. But I don't think using
> "raw" new and delete as with my_object1 would be a good idea over and
> over again from a fragmentation standpoint...

The issue here is memory fragmentation, /not/ whether a chip happens to
have an MMU or not. An MMU can help combat memory fragmentation if you
have a lot of memory - that's why it is fragmentation is not a big issue
on PC's. But an MMU alone will not fix anything.

You combat memory fragmentation in two ways. One is
allocation/deallocation patterns. On many small embedded systems, you
only ever allocate - you never deallocate memory (typically running
until someone pulls out the plug). Alternatively, you try to
de-allocate memory in at least roughly the reverse order of allocation.
The other method is smarter allocators, such as pool allocators.

[Jorgen Grahn]

On Thu, 2016-12-15, Scott Lurndal wrote:
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>>On 15.12.2016 21:39, Jorgen Grahn wrote:
>>> On Thu, 2016-12-15, bitrex wrote:
>>> ...
>>>> The C++11 STL smart pointers are out, as I guess they assume nobody
>>>> would be using them on an architecture with no MMU, where you shouldn't
>>>> really be dynamically allocating objects in raw form to the heap.
>>>
>>> I was happily using dynamic allocation on such systems in the early
>>> 1990s. So was anyone else programming e.g. the Commodore-Amiga. An
>>> MMU is not a requirement for malloc/new.
>>
>>As I recall the original Amiga used an MC68000 processor, with a 24-bit
>>address bus and MMU?

24-bit bus yes, but no MMU.

>>The 68000 was very nice.

Indeed.

> IIRC, 68030 was the first 68k with an integrated MMU. Even the
> 88100 needed an 88200 for the MMU functionality.
>
> The Amiga 1000 (sold mine recently) had a 7mhz 68000.

Yes, and even the later Amigas with 68030 or 68040 CPUs didn't use the
MMU. All processes used one common, flat, shared memory space.

(There may have been Amiga-like or -branded computers after Commodore
folded in 1994. I don't know about them.)

As a programmer you learned to clean up your resources. As a user,
you learned not to trust the system after one process had crashed.

[David Brown]

Yes, that could be an efficient implementation of the operations on
std::atomic<int> on such devices.