Im new to callbacks, I am trying to make an input buffer with a callback
so that i wont miss out inputs while doing lazy processing..

this is what i came up with

Then in main:

but after buf.end reaches 255 the program gets stuck.
The same program works perfect if i make everything in 'input' structure as separate
global variables.

There are No compile Errors

I compile with -lalleg -O -Wall in Dev-C++
Can Someone help

Change the 255 to 256 in the declaration of message queue. When you write over the 256th element, you're clobbering your control values instead.

edit: further commentary:
That's an odd error to make for someone who got the bitwise math right.
I generally haven't used locking mechanisms like that, not sure if it's a good idea or not. Testing suggests that the mouse callback is not re-entrant on windows, but of course that might vary by platform (specifically, it's probably is re-entrant on DOS, if Allegro still supports DOS). Even given that it's re-entrant though, is that really the right way to implement such a thing? I just have the impression that implementing locking yourself is a bad idea unless you're an OS or a threading implementation.
I believe it works when not in a struct due to different memory layout - the elements in the struct are generally in order in memory, while stuff outside of structs are generally in reverse order.

Sheesh !! what a silly mistake. I was rather mislead by the complexity
of callbacks into thinking that there was no problem with the code.

thanx a lot.

I was also a bit skeptic about the implementation. Are there any other
better ways to implement such a thing.

dialmformartian, how do you make sure your main routine does not read a part of the buffer that has invalid values? the 'lock' member does not guarantee you atomic access to the buffer.

I don't know. In my Allegro callbacks, I do not bother locking (A: I think it only matters on DOS, and B: I think it only matters when there is a performance anomaly).

Hm, yeah, buf.end++ should probably be moved to after the buffer entry becomes valid instead of before, or you have a race condition there. In the example code the race won't actually do anything except cause the wrong values to be displayed once in a while, but for a real-world program that could be a serious issue.

Yeah like orz said the buf.end++ should move quite fast enough unless the user is faster than the CPU in giving in inputs (does that work that way??). I just wanted to try this after seeing the CGUI source code. CGUI seemed to implement something of the sort of an input buffer, then reads the buffer and issues messages to widgets. I just didn't have the patients to figure how it works exactly. (Can any one help)

The current system "gives up" (return and discard the event) when mouse_call() and key_call() race each other.

I'd replace the whole "lock" system by a mutex to cover all operations on start and end. The locking and unlocking are only one function call, and when you use the "official" mutex functions it's much easier to verify, from reading the code, that the critical section is indeed protected.

I used a critical section. I think it would be better for you to use the library pthreads which is compatible with many platforms.

Just to make sure we're on the same page here (because it looks to me like we might, possibly, be talking about different things):
What I think axilmar was talking about, and certainly what I was attempting to agree with, is changing this:

   buf.end++; //Quickly copy stuff
   buf.queue<i>.type = 0;
   buf.queue<i>.val = f;
   buf.queue<i>.ex1 = ex1;
   buf.queue<i>.ex2 = ex2;
   buf.queue<i>.ex3 = ex3;

to this:

   buf.queue<i>.type = 0;//Quickly copy stuff
   buf.queue<i>.val = f;
   buf.queue<i>.ex1 = ex1;
   buf.queue<i>.ex2 = ex2;
   buf.queue<i>.ex3 = ex3;
   buf.end++;

The idea here being that if buf.end is incremented before buf.queue is updated, then your main loop will notice that buf.end is no longer equal to buf.start, and read out the values of buf.queue, at a time when they may or may not be initialized. By making that change, the main loop isn't told about the new mouse event until it's guaranteed to be able to correctly read buf.queue. This is known as a race condition; it is a real possibility on windows, though maybe not on DOS. It would probably be extremely rare, at least on single-core CPUs (the OS scheduler would have to preempt mouse_call after buf.end++ and before buf.lock--).

Anyway, onward:

I'm not familiar with CGUI, but I am familiar with SDL, which uses an input buffer (patterned after win32 & DirectX I think, though I haven't done much win32 and/or directX programming). It is my opinion that input buffers are superior to the polling interface that Allegro offers for large programs, but inferior for small programs. My current program extends the concept slightly... it timestamps all input, considers time to be an input, and logs all input to file, in order to allow exact program execution to be reproduced, and as a cheap (read: not very good) way to have game mechanics still feel correct when rendering is slow.

What's wrong with your current code? It appears to buffer mouse events fine. The keyboard code isn't posted, but I presume it buffers those okay also. What are you asking for beyond general commentary on the concept of input buffers in general and/or the specific implementation in CGUI?

Hey thanx Orz for clearing the confusion here.

i wanted to create input buffer system because my graph
plotter program(which uses polling) didn't seem to process events during some
humongous calculations.but i was relucatant to use CGUI coz A)i didn't want
to give away the gui system I had already pogrammed. B) I always have a do it all myself attitude.

I just wanted anybody who know about CGUI internals to comment.

So does that mean i can use this as a reliable buffer system if im not bothered of
the fact that "The current system "gives up" (return and discard the event) when mouse_call() and key_call() race each other."
as audric said. (May be i could implement mutex later) or should i go for something else like pthread.

Here it is

and it does work fine.

The only severe problem was the array[256], fixed.

Your test code to show the internals is not thread safe, but it will only cause a problem when the buffer is getting full and the buffer's head starts biting its tail.
(It should behave like: "lock, make a copy of the element, remove the element, unlock" : afterwards, you have all the time you want to process the event)
IMO, don't bother. Increase the buffer to 512, 1024 or even more if you actually run into problems. (full buffer means missed events, anyway)

The problem I pointed should not happen often, but consequences on input should be VERY weird:
Missed event: if it's a key_up, key_down, or mouse butto, it will look like a stuck key.
It will also cause an earlier entry in the buffer to be considered new, and happen again. It will be very visible as the mouse will jerk away and come back, or a key you didn't press will happen to be stuck down.

In my example I took the mutex functions that are in the pthread library, but it doesn't mean you need to multi-thread - the allegro hooks should work fine.

But allegro hooks are executed by threads other than the main one.

I would suggest to dialmformartian to use pthreads anyway. Multi-threading programming is quite tricky and sooner or later he will have untraceable problems.

Yes, Allegro uses threads internally.
Why dedicate threads yourself if the API already does things right? (and dialmformartian uses it rather correctly)
My first hint was only to use to a reliable and standard mutex system : two functions, lock and unlock. Just surround the critical sections, the closer the better.

I did not say that dialmformartian should use his own threads. I said that he should use critical sections to synchronize access to the shared variables because Allegro uses threads.

Exactly.

On further thought:

1. Threading/locking/mutexes/whatever:

So far as I can tell, the keyboard/mouse callbacks in Allegro are all executed from a single thread. Thus, there is no benefit to adding mutexes or anything like that.

Thus: don't use pthreads/whatever for this. Use of platform-dependant or other-library-specific threading primitives is unnecessary and undesirable in this context. Even the "lock" variable in the code is useless. The only kind of thead-awareness needed is the the stuff alread there - the "volatile" keyword on the buffer variables and careful ordering of when buf.end and buf.start are incremented.

2. mouse_call:

dailmformation:
You're implementation is perfectly fine as is. Here are a few things I would consider doing anyway, just because I think the resulting code easier to read or maintain or prettier or something.
2a: eliminate the branches and temporary variables - they don't accomplish anything.
this:

   unsigned int i, ex1 = 0, ex2 = 0, ex3 = 0;
  
   if(f & MOUSE_FLAG_MOVE) {
      ex1 = mouse_x;
      ex2= mouse_y;
   }
   if(f & MOUSE_FLAG_MOVE_Z)
      ex3 = mouse_z;

becomes this:
unsigned int i;
and this:

   buf.queue<i>.ex1 = ex1;
   buf.queue<i>.ex2 = ex2;
   buf.queue<i>.ex3 = ex3;

becomes this:

   buf.queue<i>.ex1 = mouse_x;
   buf.queue<i>.ex2 = mouse_y;
   buf.queue<i>.ex3 = mouse_z;

2b. Make the size of the buf.queue array be a numerical constant (an enum or #define) instead of hardwired. Do the same thing for the "type" values (currently 0 is mouse, 1 is keyboard - wrap those values in enums or #defined constants instead). That way it's easier to change the values later if there is some need to do so.
2c. So far as I can tell, there is no point to the use of buf.lock on windows (or, I suspect, any other Allegro platform). You could remove it.

3. Buffered Input:

dialmformartian: Your main loop reading the callbacks looks correct. I would suggest that that the next step be to add an interface/wrapper to hide/encapsulate the details of the buffer from the main loop or anything else that needs to read keyboard/mouse events.

ouch... sorry for all the bad advice I gave

But that thread is a different one from the main thread. Adding a mutex would prevent synchronization problems between the main thread and the allegro input thread.

Actually, it is not. There is a possibility that non valid data will be read from the buffer.

But that thread is a different one from the main thread. Adding a mutex would prevent synchronization problems between the main thread and the allegro input thread.
Each variable is written to by only one thread, all variables are volatile, and all writes are atomic. Under these circumstances, buf.start and buf.end together act as a valid synchronization mechanism, and heavier weight thread synchronization objects are not needed. You can of course use a mutex anyway, but since Allegro does not offer mutexes that would require addition library or platform dependent stuff complicating the build process and/or portability.

That was fixed by moving buf.end++. If you are saying that another issue exists, describe it more specifically.

No they are not atomic. A variable increment has 3 CPU instructions: a) load value to register, b) increase value, c) put value back to memory.

For example:

int x = 0;
x++;

becomes:

004113B5  mov         eax,dword ptr [x] 
004113B8  add         eax,1 
004113BB  mov         dword ptr [x],eax

(copied from the disassembly window of the VS debugger).

I was not refering to the whole read-modify-write aspect, only the write aspect. ie the value is always either equal to what it is before the statement or after the statement, the write portion is never split into two like it could be for a 64 bit integer.
edit: and, side note, I believe increment instructions on x86 accept memory parameters, though of course they don't on most RISC architectures

But the whole point is to make the whole thing deterministically safe. It's not a big deal to include pthreads in your source anyway.

Depends on the system. Allegro can run single-threaded on Linux (AFAIK), and has to run single-threaded on DOS. And given that the current API will be wrapped around a new API in the future, you can't know how that'll do it either. It's not good practice to assume callbacks or timers are run from a seperate thread than your program.

where do i get pthread

Right here.

Sigh.
Okay, let's this from three angles:
1. Would adding a pthreads lock to the callback change anything on any specific platform?
2. Is this the manner in which Allegro intends its callbacks to be used?
3. What is the cost of adding additional locking?

Now, the answers for each question:
1. Would adding a pthreads lock to the callbacks change anything on any specific platform?
In order for it to change something, the callback functions would have to be running concurrently with themselves on some platform. This never happens on DOS, Windows, or Linux, the 3 platforms mentioned so far in this forum thread.
DOS: the callbacks appears to happen from within an interrupt - ie with interrupts disabled so they cannot be interrupted.
WIN32: the callbacks appear to be called from a single thread which does nothing but wait for input and call the callbacks when input arrives. Since this is a single thread, it can't call another callback until the previous one returns.
LINUX: the callbacks appear to occur inside the SIGIO handler. According to the GNU docs, no signal handler is called during handling of the same signal, and since both keyboard and mouse use the same signal, neither keyboard nor mouse callbacks can run concurrently with themselves or each other.

2. Is this the manner in which Allegro intends its callbacks to be used?
Allegro documentation says that the keyboard callback "executes in an interrupt context". It doesn't say that as DOS-specific, though obviously it's not literally true for non-DOS platforms. For the mouse callback, all it says is "function must be in locked memory, and must execute very quickly", even less helpful. My interpretation is that this is the correct way to use the Allegro callbacks, though the documentation leaves this unfortunately ambiguous.

3. What is the cost of adding additional locking?
If you use Allegro's built-in locking mechanisms (_enter_critical() and _exit_critical())... well, I don't know what the drawbacks are - Allegro's built-in locking mechanisms are undocumented so far as I can tell, so I presume you're not intended to use them for normal Allegro programs.
If you use platform-specific locking mechanisms, the obvious cost is in portability.
If you use pthreads or another threading API with implementations for a variety of platforms, the obvious cost is the standard cost for adding dependancies - it makes it harder for arbitrary Allegro users to get your code running - they have to get the library themselves, and figure out how to install it and link with it. This cost is greatly reduced if you are the only one likely to compile your code. (additionally, I suspect that using pthreads calls inside a DOS interrupt is a bad idea)

edit: note: this is only considering adding locking to the callback. I would recommend adding locking to any function that reads from the input buffer if and only if your code is multithreaded independent of Allegro.

1. I don't believe pthreads EXISTS on DOS or DS.
2. You should never do anything clever in allegro timers. ever. You're just asking for trouble.
3. It just won't work on platforms without locking features.

If one is interested in running the program in DOS, then the app must be coded in a special way so as that DOS is handled appropriately.

It is not very difficult to use #ifdef to include different APIs according to platform.

Yes. It would make the program correct in those platforms that input is handled by a different thread.

Allegro has many DOSisms. Any modern library would not use the concept of interrupt to service input, but the concept of input queue. Unfortunately for us, Allegro does not do that, so there are two solutions:

1) fix Allegro to provide a mouse queue, like the keyboard queue.
2) use callbacks to implement your own queues.

I have done #2 in my GUI code.

It's minimal, because critical sections are used.

Nope, you got it wrong here. The lock will not synchronize the input threads, because there is only one input thread. The lock will synchronize the input thread and the main thread.

Exactly.

It's no big deal to do so; just a couple of #ifdefs.

The cost of debugging multithreaded programs far outweights the cost of installing and linking with a library.

Here is a very interesting link with the following quote:

No variable or structure should be accessed from multiple threads without being accessed in a thread-safe fashion.

Obviously the guy has great experience with threads and Windows, so if you don't accept my comment, please accept his.

Not if its coded properly. As long as you use Allegro properly, and don't rely on platform-specific behavior (eg. how callbacks are implemented), it'll work. However, people tend to become lax because "it's not needed right now for my target platform(s)" and thus don't bother with proper code.

And given that this will be layered on top of the new API in the future, what'll you do if all platforms, instead of just DOS, are then more sensitive to improper code? You'll pretty much lock it out of being able to use the compatibility layer of newer versions and require Allegro 4.2 only.

The only 'coded properly' technique with multiple threads is to use synchronization. Didn't you read the link I posted?

Yes, I fully agree with that. I'm talking about Allegro's callbacks, though. You can't assume whether Allegro's callbacks are threaded or not.

1. http://moss.csc.ncsu.edu/~mueller/pthreads/
2. I don't consider copying input to a buffer "clever". It's basically the ONLY thing that the input callbacks are useful for.
3. edited: hm... It won't work correctly on platforms with sufficiently weak memory coherency models. Investigating...

You conspicuously omitted the next line "Note that this applies only to variables where concurrent access can produce incorrect results". He then links to an example of his where he recommends using just volatile variables.
You might think that your position is vindicated by his next statement that incrementing a volatile integer is not thread-safe on a multi-CPU system. However that statement does not apply to the special case where only one thread modifies a variable (while other thread(s) read it).

There are three different locking scenarios we're looking at here in this thread:
locking type A: input callbacks lock to prevent reentry into the input callbacks
locking type B: input callbacks lock and input reader lock (same lock), to prevent reader from reading not-yet-ready events
locking type C: input readers lock (in a program with multiple threads, not counting those allegro created)

In that particular case, you were apparently talking about type B, while I was talking about type A. It is my position that locking types A and B are pointless. I think everyone is in agreement that type C is necessary if and only if the program is multithreaded (not counting Allegro-created threads that the user code knows nothing about).

However, I'm beginning to suspect that you might be right. After reading through a bunch of x86, PPC, and C docs, it looks like the ordering may not be guaranteed between multiple CPUs under the circumstances in which the callbacks execute on various platforms unless extra effort is made. That's somewhat scary though, as this appears to be what Allegro does internally... possibly I've been up to long, but to my current interpretation, not only is this code slightly flawed in a multi-CPU environment, but so is Allegro keyboard handling on WIN32 and OSX. And I'm not too sure about the Linux version either... executing in the SIGIO handler protects it somewhat, but only if the reading thread is the original thread, and it can also execute in a timer callback instead, or from the main thread if simulate_keypress is called...

Will think more tomorrow. Hopefully.

edit: fixed typo and changed #3 at the top

Well, if the game/library needs to behave correctly in the 90% of the computers out there (i.e. those that run Windows), you need to code threads properly.

Incrementing an integer is not thread-safe, period. If you read the whole thing, you would have seen the analysis of the assembly code.

You are just asking for trouble especially when the integer is an index to a buffer.

No sh1t, Sherlock! :-)

CPUs have gone multicore, you have forgotten that???

You seem to be ignoring the point of that: when a variable is only written to by one thread, the atomicity of the entire read-modify-write operation becomes irrelevant. Only the atomicity of the write operation itself is relevant, because the variable cannot be modified asynchronously to that code (because only one thread modifies it). And the write is generally atomic, provided that the integer is aligned (caveats: not true on 386sx when paired with a 32 bit compiler, some 8 bit CPU/compiler combinations, a few other arcane places... but to get even a remotely possible failure you have to find a platform that uses one of the handful of CPUs on which that's not true, uses multiple CPUs concurrently, and runs Allegro programs; you'd have an easier time finding a system that uses 10 bit bytes).

That is the part I'm agreeing with now - that using the variable as an index into a changing buffer is unsafe. According to my current understanding, this code has the capacity to return garbage input (though it almost never will). It could be fixed with threading libraries, platform specific locking mechanisms, or more exotic coding methods. However, I think that the Allegro internals have the same flaw in them, so you suffer from this flaw regardless...

I remembered the multicore part, but did not realize that Intel and others had weakened their memory coherency policies (I expected at least PRAM consistency for writes to volatile variables). And I presumed that Allegro would arrange things in such a way that its input callbacks were usable in a safe manner without extra dependencies or extraordinary effort.

edit:

ARRGHH!
Okay, I was too tired when coming to the conclusion that it wasn't safe. x86 DOES still offer strong memory coherency, I misread the docs as saying the opposite of what they said. Here's my current position (hopefully I will slow down the rate at which I change positions soon):

The code is correct on some platforms only.
Allegro code is correct on some platforms only.
Which platforms?

x86/*: Allegro and this code both work, because of strong memory coherency guarantees on normal x86 systems.

non-x86/linux: Allegro and this code probably work correctly, if the user code is totally single-threaded. Merely having only one thread talk to allegro is not enough though - it must also be the thread that handles signals. On x86 specifically the issue is (I think) irrelevant though because of the x86/* strong coherency guarantees. However, the buf.lock mechanism should be kept, because in (very rare) cases the callback can become reentrant.

PPC/macOSX: Allegro and this code are both incorrect on this platform.

PPC/macOS9 and x86/DOS: Allegro and this code are correct, because (I think) the code all executes in interrupt context anyway.

You went into all this trouble just to prove what others said from the beginning? :-)

And to submit a bug report : )

http://www.allegro.cc/forums/thread/590120