[erlang-questions] compare and set semantics using ets?

[Anton Lebedevich]

Hello.

Is it possible to implement atomic compare-and-set semantics using ets?

Currently it allows to increment counter and return new value atomically
but "don't touch the counter if someone touched it before me" is quite
tricky or impossible to achieve.

I might be digging in a wrong direction, the problem is following:
There is a shared limited resource (i.e. memory). Incoming requests
require some (specified in headers) amount of the resource which is
freed on completion. Each request is served via it's own process. The
process needs to allocate the resource and serve the request or refuse
if there is not enough resource available.

Simple (and slow on high request rate) solution is to implement
gen_server that handles allocation requests and either grants them or
refuses based on calculated total.

https://github.com/ferd/dispcount uses ets counter with known initial
value to implement compare-and-set but in my case the initial value
(currently allocated amount) is unknown.

Regards,
Anton Lebedevich.
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

[Max Lapshin]

You want something like iptables -L which atomically tells you current value and reset it.

[Anton Lebedevich]

On 01/14/2013 04:24 PM, Max Lapshin wrote:
> You want something like iptables -L which atomically tells you current
> value and reset it.

You'll need -Z flag for iptables to actually reset counters.

Here's the description of compare and set (or swap):
http://en.wikipedia.org/wiki/Compare_and_swap

[Dmitry Kolesnikov]

Hello,

not it is not possible w/o touching VM.
I've started to implement "advanced counters" via dedicated process.

BTW, you approach with manager process is aligned with OTP principles.

- Dmitry

[Jesper Louis Andersen]

On Jan 14, 2013, at 1:08 PM, Anton Lebedevich <mab...@gmail.com> wrote:

> Is it possible to implement atomic compare-and-set semantics using ets?

Only in a limited fashion. I guess we either need a specific CAS-instruction, or you have to look up how it is achieved in mnesia, which does to transactional updates.

CAS would relate to modern hardware implementations of software transactional memory.

Jesper Louis Andersen
Erlang Solutions Ltd., Copenhagen

[Anton Lebedevich]

On 01/14/2013 07:01 PM, Jesper Louis Andersen wrote:
> On Jan 14, 2013, at 1:08 PM, Anton Lebedevich <mab...@gmail.com> wrote:
>
>> Is it possible to implement atomic compare-and-set semantics using ets?
>
> Only in a limited fashion. I guess we either need a specific CAS-instruction, or you have to look up how it is achieved in mnesia, which does to transactional updates.

Good catch, I've completely forgot that mnesia already does it, will
take a look at its sources.

> CAS would relate to modern hardware implementations of software transactional memory.

One word CAS (Intel CMPXCHG) doesn't need bleeding edge hardware, it has
been there for quite a long time.

Regards,
Anton Lebedevich.

[Anton Lebedevich]

On 01/14/2013 07:13 PM, Anton Lebedevich wrote:
> On 01/14/2013 07:01 PM, Jesper Louis Andersen wrote:
>> On Jan 14, 2013, at 1:08 PM, Anton Lebedevich <mab...@gmail.com> wrote:
>>
>>> Is it possible to implement atomic compare-and-set semantics using ets?
>>
>> Only in a limited fashion. I guess we either need a specific CAS-instruction, or you have to look up how it is achieved in mnesia, which does to transactional updates.
>
> Good catch, I've completely forgot that mnesia already does it, will
> take a look at its sources.

Reading mnesia sources revealed that it uses transaction manager and
locker processes to serialize modification operations.
Mnesia transactions rely on making modifications sequential not on
CAS-instructions.

It turns out that CAS which is a workhorse of many non-Erlang concurrent
libraries isn't available in Erlang without NIFs. Am I missing something?

[Max Lapshin]

Why are you speaking about some CAS instructions, when you just need API in ets module: insert_or_replace