mutexes and const_iterators

[Angus]

Hello

I am using a map which holds a list of client connections (to a server).
When a client connects a client gets added to the map and also when a client
disconnects.

In various parts of the code the map gets updated - the key is an int and
the value is a class.

As the map may be accessed by multiple threads I use a mutex to control
access - ie locking whenever an item is added or removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access the item via
an iterator.

2. Do I need to lock if I simply access the map via a const_iterator?

Angus

 

[Barry]

Hello

I am using a map which holds a list of client connections (to a server).
When a client connects a client gets added to the map and also when a client
disconnects.

In various parts of the code the map gets updated - the key is an int and
the value is a class.

As the map may be accessed by multiple threads I use a mutex to control
access - ie locking whenever an item is added or removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access the item via
an iterator.

2. Do I need to lock if I simply access the map via a const_iterator?

I think this is a reader-writer problem, nothing specific with /map/.

one note:
23.1.2/8
The insert members shall not affect the validity of iterators
and references to the container, and the erase members shall
invalidate only iterators and references to the erased elements

 

[Kai-Uwe Bux]

Hello

I am using a map which holds a list of client connections (to a server).
When a client connects a client gets added to the map and also when a
client disconnects.

In various parts of the code the map gets updated - the key is an int and
the value is a class.

As the map may be accessed by multiple threads I use a mutex to control
access - ie locking whenever an item is added or removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access the item
via an iterator.

2. Do I need to lock if I simply access the map via a const_iterator?

The standard does not (yet) discuss any multi-threading issues. Therefore,
you have to have a look at the thread safety guarantees that your STL
implementation offers. Chances are that if there is a thread that modifies
the map, all access (including read-only access through iterators) has to
be locked; if _all_ threads operate read-only on the map, you might not
need to lock. However, to be sure you have to check the documentation of
your standard library implementation.


Best

Kai-Uwe Bux

 

[Paavo Helde]

Hello

I am using a map which holds a list of client connections (to a
server). When a client connects a client gets added to the map and
also when a client disconnects.

In various parts of the code the map gets updated - the key is an int
and the value is a class.

As the map may be accessed by multiple threads I use a mutex to
control access - ie locking whenever an item is added or removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access the
item via an iterator.

As already mentioned, threads are outside of standard so not guarantees
here.

Note first that here the locking problems appear on two levels: map and
item. For map you definitely have to have some locking.

If you obtained the item iterator while the map was locked, then there
are good chances that you can dereference the iterator later and get to
the item without locking. If you are obtaining the iterator in a
multithreaded regime, then you have to lock the whole map. Just imagine
what happens if one thread is searching for an item in the map search
tree and the other thread comes along and inserts a new node, modifying
the tree beneath your feet!

The dereferencing of iterators in different threads is still suspect. A
paranoid debugging implementation of <map> might check during this
operation that the corresponding map is alive and the iterator is valid
inside there. To be on safer side, you can convert the iterator into a
plain item pointer before releasing the map lock. This breaks any
connection to the map, you have a plain pointer and your application
logic is now responsible for that the pointer remains valid while used.

Of course, as the map is global, different threads can obtain a pointer
to the same item. If they always do only read-only access (physically),
then there is no problem and no need for locks. However, because one of
the threads finally modifies the item (when destroying it), the things
are not so simple. If your application logic cannot guarantee that the
items are only referenced by a single thread when deleted, then you
should hold the whole map lock always when working with any item in the
map. For read-only access the items can be copied out of the map, to
release the lock faster.

One way to achieve the above guarantee (single-thread visibility by
destruction) is to use reference-counted smartpointers to the items in
the map (these have to be threadsafe smartpointers, with locked
refcounter increment/decrement). This ensures that the object can be read
and destroyed safely (but not modified at the same time, for that you
would need other mutexes/locks).

2. Do I need to lock if I simply access the map via a const_iterator?

The 'const' in 'const_iterator' here is applied only to the items
themselves, so no change with respect to map locking. Also, the const can
be cast away and worked around by mutable members. What is important is
whether the items are modified physically while in map or not. Using
const_iterator can help here, but not more. Most importantly, you can't
delete the items from the map by const_iterator, so you probably cannot
follow this policy strictly.

hth
Paavo

 

[Jim Langston]

Hello

I am using a map which holds a list of client connections (to a
server). When a client connects a client gets added to the map and
also when a client disconnects.

In various parts of the code the map gets updated - the key is an int
and the value is a class.

As the map may be accessed by multiple threads I use a mutex to
control access - ie locking whenever an item is added or removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access the
item via an iterator.

Consider. Some other thread has looked up the entry previously and is
working on it for some reason. Your current thread decides to update the
item. So you write to it without a lock. The other thread then finishes
what it's doing, but it's logic was based on the information inside the
class before it was updated, which it never saw because it read it before
the update.

2. Do I need to lock if I simply access the map via a const_iterator?

Say your thread grabs a const_iterator without a lock. Now another thread
grabs the item for maintainance. Your current thread thinks it has the
latest information while the other thread is busy changing the information.

Threads are really OT in this newsgroup because there are a lot of issues
with them other than just mechanics that go far beyond the C++ langauge.
You should subscribe to comp.programming.threads which deals with threads in
general and all the issues invovled.

The questions you are asking are not C++ questions, they are
thread/programming questions.

 

[James Kanze]

I am using a map which holds a list of client connections (to
a server). When a client connects a client gets added to the
map and also when a client disconnects.

In various parts of the code the map gets updated - the key is
an int and the value is a class.

As the map may be accessed by multiple threads I use a mutex
to control access - ie locking whenever an item is added or
removed.

I have these questions:

1. Do I also need to lock if I just update and item? I access
the item via an iterator.

And what is supposed to happen if another thread removes the
element you're updating, while you're updating it?

2. Do I need to lock if I simply access the map via a const_iterator?

And what is supposed to happen if another thread removes the
element the iterator points to, thus invalidating it?

The answer to your questions is yes and yes. In this case,
there are obvious scenarios in which the code breaks otherwise.
The rule, however, is far more general, and doesn't depend on
such scenarios: if any thread may modify the object, *all*
accesses to the object must be externally synchronized. Period.
There are no exceptions. An iterator into a map accesses (parts
of) the map, and an element in the map is considered part of the
map. (In practice, I think that if you can somehow guarantee
that the element in question is not itself being removed or
modified in any way, you can probably get away with 1, although
I suspect that the final standard will say that even that is
undefined behavior.)

 

[James Kanze]

The standard does not (yet) discuss any multi-threading
issues. Therefore, you have to have a look at the thread
safety guarantees that your STL implementation offers. Chances
are that if there is a thread that modifies the map, all
access (including read-only access through iterators) has to
be locked; if _all_ threads operate read-only on the map, you
might not need to lock. However, to be sure you have to check
the documentation of your standard library implementation.

Those are the guarantees for all of the implementations I'm
aware of, and is doubtlessly the guarantee which will be adopted
by the final standard. IMHO, it still leaves open something
like the following:

std::string const* ps = NULL ;
{
std::mutex::scoped_lock l( mapMutex ) ;
ps = map.find( index )->second ; // Imagine error checking
}
std::cout << *ps ;
// or *ps = ...

Are the accesses through ps considered to be accesses to the
map. (I would say yes, but... I can't conceive of an
implementation where the std::map code would actually access the
non-key string value in any way, unless it was removing the
element from the map.)

 

[James Kanze]

innews:[email protected]:

As already mentioned, threads are outside of standard so not guarantees
here.

Not for long.

Note first that here the locking problems appear on two
levels: map and item. For map you definitely have to have some
locking.

That is an interesting question, of course. Are the items part
of the map, or not?

If you obtained the item iterator while the map was locked,
then there are good chances that you can dereference the
iterator later and get to the item without locking.

Almost certainly not. Dereferencing the iterator accesses the
map.

If you are obtaining the iterator in a multithreaded regime,
then you have to lock the whole map. Just imagine what happens
if one thread is searching for an item in the map search tree
and the other thread comes along and inserts a new node,
modifying the tree beneath your feet!

Practically speaking, you have to acquire a lock on the map
before getting the iterator, and hold it until you finish using
the iterator.

The dereferencing of iterators in different threads is still
suspect. A paranoid debugging implementation of <map> might
check during this operation that the corresponding map is
alive and the iterator is valid inside there.

And if it doesn't check, using the iterator when this is not
true is undefined behavior.

To be on safer side, you can convert the iterator into a plain
item pointer before releasing the map lock. This breaks any
connection to the map, you have a plain pointer and your
application logic is now responsible for that the pointer
remains valid while used.

Do you have a guarantee of this somewhere? It's obviously not
true if the other thread erases the element from the map, but
I'm not really sure that it's true if if the other thread does
anything which modifies the map. Element level locks are only
valid if you can guarantee no insertions and no deletes in the
map while you hold them. (The usual case where they are used in
in a map which is rarely updated. Client code acquires a rwlock
for read on the map before getting and locking the element.)

Of course, as the map is global, different threads can obtain
a pointer to the same item. If they always do only read-only
access (physically), then there is no problem and no need for
locks. However, because one of the threads finally modifies
the item (when destroying it), the things are not so simple.
If your application logic cannot guarantee that the items are
only referenced by a single thread when deleted, then you
should hold the whole map lock always when working with any
item in the map. For read-only access the items can be copied
out of the map, to release the lock faster.

One way to achieve the above guarantee (single-thread
visibility by destruction) is to use reference-counted
smartpointers to the items in the map (these have to be
threadsafe smartpointers, with locked refcounter
increment/decrement). This ensures that the object can be read
and destroyed safely (but not modified at the same time, for
that you would need other mutexes/locks).

I would very definitely avoid reference counted smart pointers
anywhere the objects could be accessed from multiple threads.
Reference counting means that other threads may end up modifying
a shared object "behind the scenes", without the client code
really being aware of it.

 

[Paavo Helde]

(Note: this is becoming very off-topic, the right group would be
comp.programming.threads).

[...]

That is an interesting question, of course. Are the items part
of the map, or not?

That depends on the application design.

Almost certainly not. Dereferencing the iterator accesses the
map.


Practically speaking, you have to acquire a lock on the map
before getting the iterator, and hold it until you finish using
the iterator.


And if it doesn't check, using the iterator when this is not
true is undefined behavior.

Yes, you are right.

Do you have a guarantee of this somewhere? It's obviously not

23.1.2 [lib.associative.reqmts] says:

-8- The insert members shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate only
iterators and references to the erased elements.

I am not very strong in standardese, but I understand this so that a
plain pointer to an item is holding such kind of reference which is
guaranteed to remain valid by the standard.

Deletion of the item would of course invalidate the pointer, hence the
refcounting trick I talked about.

true if the other thread erases the element from the map, but
I'm not really sure that it's true if if the other thread does
anything which modifies the map. Element level locks are only
valid if you can guarantee no insertions and no deletes in the

I believe insertions and deletions of unrelated items are OK, they don't
affect the lifetime and memory location of the locked item; also, no
sane map implementation would read or modify the content of unrelated
items (it may read map keys for comparisons, but not the stored items). I
guess this is not guaranteed by the standard because it does not contain
any multithreading issues, but I would expect this to hold for all
implementations which support multithreading.

map while you hold them. (The usual case where they are used in
in a map which is rarely updated. Client code acquires a rwlock
for read on the map before getting and locking the element.)



I would very definitely avoid reference counted smart pointers
anywhere the objects could be accessed from multiple threads.
Reference counting means that other threads may end up modifying
a shared object "behind the scenes", without the client code
really being aware of it.

The code potentially modifying the shared object is also client code -
the map won't touch your items unless asked. So nothing happens 'behind
the scenes'. And refcounting does not protect against modifications, it
only protects against unexpected deletion of the object.

In the end this is a question of perfomance and (possibly premature)
optimization. In a multithreaded server application you want to release
any global lock ASAP. This means that once you have found your item in
the map, you have either to perform the operation on the item
immediately, or copy out the needed information, release the lock and
perform the operation later. Which way is appropriate depends on the
application requirements. First way is definitely simpler and easier to
get right. However, if the performance issues dictate the second
approach, then about the absolute minimum of information which can be
copied out is the raw pointer to the item. Alas, this brings the item
ownership, item-level locking and item destruction problems we are
talking about. So this approach should be taken only if performance
issues absolutely demand it. I should have been clearer about this in my
first post.

Best regards
Paavo

 

[James Kanze]

Paavo Helde a écrit :

news:7e997e8e-3daa-44eb-8744-07fac88a6b2e@u72g2000hsf.googlegroups.com:

(Note: this is becoming very off-topic, the right group would
be comp.programming.threads).

Not necessarily. We are talking about guarantees which are
given by std::map.

[...]

Note first that here the locking problems appear on two
levels: map and item. For map you definitely have to have some
locking.

That is an interesting question, of course. Are the items part
of the map, or not?

That depends on the application design.

It depends more on the contract that std::map specifies. As it
is currently written in the SGI pages, I think that they are.
On the other hand, as implemented (in the implementations I know
of), the restriction isn't necessary.

[...]

23.1.2 [lib.associative.reqmts] says:

The insert members shall not affect the validity of
iterators and references to the container, and the erase
members shall invalidate only iterators and references to
the erased elements.

I am not very strong in standardese, but I understand this so
that a plain pointer to an item is holding such kind of
reference which is guaranteed to remain valid by the standard.

Yes, but the above doesn't say anything about accessing through
the pointer if another thread is modifying the map.

Again, I'm concerned about guarantees. I *think* that with the
usual implementation, there should be no problem (supposing, of
course, that the modifications in the map don't delete the
object your using). The fact that a pointer is valid doesn't
mean that you can access through without synchronization.

If I understand the SGI guarantees correctly: a container
includes all of its elements as part of the container. Thus,
any access to an element in the container, regardless of how, is
invalid if the container is being modified.

Of course, this also means (literally) that using element locks
on a container whose topology isn't modified is also undefined
behavior. Which doesn't seem right, and certainly isn't
necessary. I think it's an aspect that the committee will have
to address. (Threads are already part of the current working
draft.)

Deletion of the item would of course invalidate the pointer,
hence the refcounting trick I talked about.

I believe insertions and deletions of unrelated items are OK,
they don't affect the lifetime and memory location of the
locked item; also, no sane map implementation would read or
modify the content of unrelated items (it may read map keys
for comparisons, but not the stored items).

The problem with this is that you are interpolating into the
implementation of the container for the guarantee. I agree that
it does seem reasonable for the containers to offer this
guarantee. I'm not sure that any do, though.

I guess this is not guaranteed by the standard because it does
not contain any multithreading issues, but I would expect this
to hold for all implementations which support multithreading.

I suspect that in practice, it does. But there doesn't seem to
be any guarantee of it that I can find.

The code potentially modifying the shared object is also
client code - the map won't touch your items unless asked. So
nothing happens 'behind the scenes'. And refcounting does not
protect against modifications, it only protects against
unexpected deletion of the object.

What I mean was modification of the reference counter itself.

In the end this is a question of perfomance and (possibly
premature) optimization. In a multithreaded server application
you want to release any global lock ASAP.

But no sooner.

This means that once you have found your item in the map, you
have either to perform the operation on the item immediately,
or copy out the needed information, release the lock and
perform the operation later. Which way is appropriate depends
on the application requirements. First way is definitely
simpler and easier to get right. However, if the performance
issues dictate the second approach, then about the absolute
minimum of information which can be copied out is the raw
pointer to the item. Alas, this brings the item ownership,
item-level locking and item destruction problems we are
talking about. So this approach should be taken only if
performance issues absolutely demand it. I should have been
clearer about this in my first post.

What I would hope (but I don't see the official guarantees there
yet) is that:

if no thread is modifying the topology of the container
(i.e. adding or removing elements), some sort of element
level locking could be used, and

if the container is only rarely modified, some sort of
read/write lock on the container, combined with element
level locking could be used.

I'm not quite sure how to formulate this in standardese,
however. Especially as I don't think that the standard will
contain rwlocks, at least in the next version.

 

[Paavo Helde]

(e-mail address removed):
[...]

What I mean was modification of the reference counter itself.

Yes, each refcounter has to be protected by their own mutex (or use
atomic increments/decrements if available on the platform). These are not
global locks like the one used for locking a global map, and the locking
is in force only for a very short time (one memory read-write cycle), so
in the light of a multithreaded high-performance server application this
is a totally different kind of lock than the one locking the global map
of connections.

Modification of the refcounter 'behind the scenes' means that some other
thread has decided to use the same object at the same time, possibly
prolonging its lifetime. If the "users" of the object cannot cope with
such kind of shared ownership, then this strategy cannot be used. For
example, if the removal of the object from the global map means its
logical death, then it should not be used in later in any threads even if
they happen to have stored a smartpointer to the object from earlier
times. On the other hand, using of "out-dated" objects might be benign
and of no concern - this fully depends on the application on hand. This
is what I meant by saying that the ownership of map items depends on the
application.

Otherwise, I think we agree in most points. I am relying more on "sane"
implementations of std::map and unit tests, and you are more relying on
guarantees offered by standards. In real word you cannot rely 100% on
standards anyway, all complex software contains bugs which you have to
work around regardless of what the guarantees are saying. Some boost
libraries are sprinkled with workarounds all over the place. I'm not
saying this is a good thing, but this is the reality.

best regards
paavo