Web Prolog ISOBASE Test Cluster - Hack Away, Find Security Bugs

Looking for Group
37

I’m not familiar with shared tabling, and therefore I’m not sure what you’re saying here. But I’d like to try to respond to the following question.

Let me try to explain how it works with respect to the following implementation:

:- http_handler(root(ask), http_actor_manager, [spawn([])]).

http_actor_manager(Request) :-
    http_parameters(Request, [ 
        query(QueryAtom, []),
        offset(Offset, [integer, default(0)]),
        limit(Limit, [integer, default(1)])
    ]),
    read_term_from_atom(QueryAtom, Query, []),
    query_id(Query, QID),
    (   retract(cache(QID, Offset, Pid))
    ->  self(Self),
        pengine_next(Pid, [
            limit(Limit),
            return_to(Self)
        ])
    ;   pengine_spawn(Pid),
        pengine_ask(Pid, offset(Offset, Query), [
            limit(Limit)
        ])
    ),
    receive({
        failure(Pid) ->
            respond(failure);
        error(Pid, Exception) ->
            respond(error(Exception)) ;
        success(Pid, Solutions, true) ->
            Index is Offset + Limit,
            assertz(cache(QID, Index, Pid)),
            respond(success(Solutions, true));
        success(Pid, Solutions, false) ->
            respond(success(Solutions, false))   
    }).
  
query_id(Query, Query).

(Note that I’ve simplified query_id/2 in order to make my line of reasoning easier to follow.)

Suppose this is the current cache:

cache(mortal(_), 1, 55321100).
cache(mortal(_), 1, 66783421).
cache(p(_),      3, 84926378).

And suppose two identical requests of the following form are made at the same time:

GET http://ex.org/ask?query=mortal(Who)&offset=1

When they try to retract the first cache/3 clause, only one of them will succeed. (At least that’s how I understand the documentation on retract/1 at retract/1) It will thus grab the pengine with the pid 55321100. The other request will grab the pengine with the pid 66783421.

For a short while, there will only be one clause in the cache, namely

cache(p(_), 1, 84926378).

but when both requests have returned their responses, the cache has been updated and might look as follows:

cache(p(_),      3, 84926378).
cache(mortal(_), 2, 66783421).
cache(mortal(_), 2, 55321100).

So far, since retract/1 is an atomic operation, nothing bad has happened. And AFAICS, in this scenario, nothing bad can happen. So far, I see no need for a mutex.

However, the above implementation is not complete. We also need a mechanism that will prune the cache when it its max size is exceeded. Suppose the max size is 3. (Of course, normally it would be 1,000, or 10,000, or something like that.)

Now, suppose the following request is made:

GET http://ex.org/ask?query=member(X,[a,b])&offset=0

The cache will be of no help here, so a new pengine will be spawned which will do the job. Since there are more solutions, a clause will be added to the cache:

cache(p(_),            3, 84926378).
cache(mortal(_),       2, 66783421).
cache(mortal(_),       2, 55321100).
cache(member(_,[a,b]), 1, 98237833).

Now, the cache has exceeded its max size and must be pruned. This is done from the top since that’s were we have the oldest entry. The clause cache(p(_),3,84926378) must be removed and the pengine with the pid 84926378 must be forced to terminate.

This is where we have a potential race condition. Because when the pruning mechanism tries to retract cache(p(_),3,84926378), there may also be an incoming request of the form:

GET http://ex.org/ask?query=p(X)&offset=3

We have two cases:

  1. The incoming request retracts the clause cache(p(_),3,84926378) before the pruning mechanism has a chance to do so. The pruning mechanism will then instead retract cache(mortal(_),2,66783421). This, AFAICS, won’t lead to any problems.

  2. The pruning mechanism retracts the clause cache(p(_),3,84926378) before the incoming request has a chance to do so. This only means that the incoming request needs to spawn a new pengine. No problem here either.

There is no need for a mutex in the context of the pruning mechanism either. The “entry point” into the cache is always through the atomic retract/1. Once a thread has succeeded in retracting a cache/3 clause, no other thread can get at it, and thus no other thread can get hold of the corresponding pengine. (Note that for each pengine in the system, there can exist at most one cache/3 clause.)

I know only too well how difficult programming with concurrency becomes in the presence of shared state, so I’m perhaps a bit too optimistic when I boldly claim that 1) the proposed scheme will work, and 2) that there is no need for mutexes. (I thought there was, but I now believe there isn’t.)

Do you, or anyone else, see any holes in my line of reasoning?