parshing county, Nevada - continues

So what is parsing ???.

Defintion - A parsing function is a function that tries to parse thru a bit stream. This is a recursive definition!

At it's basic tenate, it is a step to take a stream and try to interpret. So for example, you just got a buffer full of bits, and one program (i.e. a parsing function) says, well it is a bit stream or byte stream or char stream. These are almost always NULL parser(s). Some has underlying, albiet very small, assumption, and some don't have any at all!. Stop for a moment, and see which has those assumptions!! What I mean here? Well, at its lowest level a bit is an identifiable unit. But for our purpose, it is more interesting to interpret as a part of a larger thing. For example, a nibble, a byte, a char, a number. So there are those assumptions. These may not be interesting while we talk about parsing, but is another fundamental assumption that we need to understand. Also getting bigger picture, almost always gives us a step foward to our understanding of things. For example, a parser usually deals with a token! So what is a token? It definitely has some assumption, and I wlll leave it at that... But the main point is  alphabet / separator / terminator etc. That I will discuss soon.

Now let say, given a stream of chars, a parsing function parses to say that it is a sentence for english language. And yet another took a stream of chars, and says it is a valid arithmetic expression. What is common here is an underlying rule that the function is trying to recognize. The rule is an english grammer in the first case, and an Algebra rule in the second case.

If you ask "Is there a possiblity, that a given stream can be interpreted as two different rules ... ?", then you will be right into the theory behind parsing - Autometa Theory. But we are going there, not yet at least...

Definition of a Parser - A parser is a program that implement a rule. A NULL parser don't implement any rule. A rule is usually a specification to recognize something like: a valid ip address; a valid statement of a computer language etc.

When a specification for a rule is used, it is usually thru a wide variety of techniques. One such powerful and robust technique is regular expression. A regular expression recogmize a regular language over a defined set of alphabet.  For the definition of alphabet, and regular langagues, please see wiki.

 As a very simple example, assume that we need to parse a string buffer and find out if it is a valid ip address or not. What is a valid ip address, you may ask!... A valid ip address is in the form of nnn.nnn.nnn.nnn in ipv4 version, where n is any number from the set {0, 1, ... 9}. A leading zero in any of those four parts, separated by dot (.) character could be allowed for simplicity. So 001.02.3.4 could be a valid ip address.

 

Now write a C program to see for yourself. This usually takes a bit of thought to program correctly ! I would try first, as if I never seen regular language and regular expression. Then we will go about definining a regular expression...

 

ip address  == [0..9][0..9][0..9].[0..9][0..9][0..9].[0..9][0..9][0..9].[0..9][0..9][0..9]

 

As you can see, leading zeros are allowed!. Now we can refine it if we want to. Then we will write program to test the specification and implementation is correct or not.

 

History - When regular expression, and parsing became a branch of science and widely popular, not many application of the technique were found beyond compiler and tools writer. Then came the internet and parsing became almost essential in the WWW technology. The result is that lot of languages now provide some kind of support to define regular expression using the underlying regular language, and parse information based on the definition of the expresssion. To name a few: Perl, Python, C++, C#, and Java.

 

More ...

Posted on Sunday, June 23, 2013 at 09:23AM by Registered CommenterProkash Sinha | CommentsPost a Comment

It's parshing county, Nevada. Wild wild west

It's parsing and not much different from what I said in the title. Yes, it is wild wild west. As you go along doing your day to day business, no matter how hard you try not to think about it, you eventually end up with stuff that you will feel that it is in your finger tips or you it is far out!

Parsing is one such thing when you try to program. I've  seen many different mistakes and not so intuitive for lot of people ( including me). So what is parsing, pattern matching etc.???

A bit of a history first, if you don't happen to know. Long long back, computers were very specific to do one type of computation or other. So there were computers for scientific computation, some were for massive data proccessing and business computations. So a genralization effort brought them together to have universal ( sort of ) computers where you can do many different types of computations. Currently, it is just simply taken for granted.

Now, for tackling interesting and somewhat big problems, there were already few languages sutiable to specific use, instead of using almost machine level language Assembler. For example, Fortran for scientific computation, Cobol for business computation.  There were others that came, did their service, and went away. Since some of these languages were to solve specific types of problems, they were bit awkward for other types of problems. Moreover, the I/O systems were thoughtout to  have block level interfaces ( specially to optimize system performance), and was directly exposed to the programs.

A major shift was that the I/O should be represented as a stream of something, and let the program interpret the way it wants. Most successful of this effort is the birth of C language, where stream of something was stream of characters. And the encoding for character is ASCII. Computer needs bits and bytes, not characters, not a word, not some formula... nothing.

So given a character stream what should I interpret it to, and how? This is where parsing comes to play. Basically what it means is that I, the program, want to interpret this stream this way, I know I can get meaningful information out of it.

No wonder, it is parshing county, Nevada in around 1850! Wild wild west, everyone has her own rule and interpretation!!

 

Parsing, to me still very elegant art, Art of Programming. It is mostly used to parse streams for computer language statment validation/interpretation. It has a rich foundation of computer science. Scanning a stream, giving it meaningful representation, then parsing is heart of computer languages and lots of other things. And to appreciate the beauty, and its non intuitive nature, just try to code up a program to parse a stream of text, and findout out if there is a valid c program statement. To be more specfic -

int main(){;;;;; return 0);} -  Is it a valid c program? And insert a dot ( . ) somewhere to see what it says. Very soon we will see that if-then-else, switch etc. going to make the program a living mess. And two questions we will have to answer (1) Is it correctly interpreting (2) Is it efficient?

So there has to be a science behind it too!!. If not, then why not would be the question for inquiring minds.

 

 

More...

Posted on Saturday, June 15, 2013 at 07:58AM by Registered CommenterProkash Sinha | CommentsPost a Comment | References1 Reference

May I be the ring master?... Please!

One of the old tool of the trade is to craft a ring buffer for quite a few things to be used it for! If you, the reader did not hear it yet, you will hear it soon!!!

So what is it? And what is the use?

Well, sometime you just want to know the recent history of certain things, say kernel events, or the recent acitivities of a server or even your application. So you want to constantly  pump out trace messages to a buffer, but your buffer might have some restrictions in terms of how much memory you should allocate for it. And optionally, you might have a backing up procedure which will do the backup ( or rather write to a file) intermittently so as to assume that if you loose the buffer information, at least you expect the file would be there to take a peek.

While this can be used in a variety of situations, we need to understand one thing is that the paradigm I try to follow is "Coding for debugging"... So anyone can have an infrastructure, more on this later, to be dropped and use in your software for debugging and other stuff...

When I try to develop some code, one thing I try to keep in my head is to have it as a reusable code. Then the otherthing I want to follow is that can I try it in user mode code, before bringing it in to kernel.... And finally can I have some way to introduce debugablity into it, from the primitive printf and cousines to elegantly using language features!!!

In this example, the ring size is fixed, in terms of how many elements it can hold. For dynamic sizing it would have to be changed. There are situations, depending on how much memory is available in the computer, the ring size has to be self tunned, which necessiates it to be dynamically sized ring. Another missing part is intermittent flushing into a file, and yet another part is missing is how to use the language features to debug this infrastructure...

I would not go into the dynamic sizing, it could be another note based on request(s).

For intermittent flushing to a file, one of the approach is to run another thread that will act as a consumer, and take the ring buffer to a file. Not very difficult to do that either.

For the language use, why do we need this? Well, the message producer could be an aribitrary source, and then the ring buffer thread would be an intermediaries ( like the way cache works), and consumer would be another thread. So one question would be -  how can I bypass the ring, and want to see the producer is producing, and consumer is directly taking it from producer and writing to file. For this an elegant solution is to have virual functions that can be redirected on the fly using lazy binding. So it would take only one line change to direct the messages to file, instead to ring....

Succently, the producer of the ring could produce nothing at all or it could produce to the ring or it could produce directly to final destination, the file or it could produce to both with or without any assistence from cosumer of the ring. And if we cover all these cases, it would be easy to find the problem component of the infrastructure.

The base code for such a ring is given as an example, but full implemenation for handling dynamic binding and debuggin including producing in a lifo or fifo are intentionallly left out for now. A c++ class based using pure virtual functions and threading works just fine for me -

 

#include <stdio.h>
#include <Windows.h>

#define SIZE_DMESG 256

//ouput level
typedef enum _DMESG_LVL{
DMESG_DISBLED,
DMESG_QUITE,
DMESG_MODERATE,
DMESG_VERBOSE,
DMESG_UNKNWN_LVL
}DMESG_LVL;

typedef struct _DMESG{
DMESG_LVL lvl;
size_t msglen;
CHAR * msg;
}DMESG, *PDMESG;

typedef struct _DMESG_RING{
ULONG producerIdx; //current producer index
ULONG ringSize; // Number of dmesg messages the ring will hold at most.
KSPIN_LOCK queuedSpinLock; //multi-proc efficient spin-lock
DMESG **pDmesgArray; // ring Array of dmesges
}DMESG_RING, *PDMESG_RING;

PDMESG_RING g_pDmesgRing;


PDMESG_RING
AllocdmesgRing( ULONG ringSize )
{
PDMESG_RING pdmesgRing;

//allocate/init Ring structure that holds meta data and the ringbuffer
pdmesgRing =(PDMESG_RING) malloc(sizeof(DMESG_RING));

if ( !pdmesgRing){
goto ErrorExit;
}
memset(pdmesgRing, 0, sizeof(DMESG_RING));
pdmesgRing->ringSize = ringSize;
pdmesgRing->producerIdx = 0;

//Now allocate the buffer array ptrs to DMESG of length ringSize
pdmesgRing->pDmesgArray =
(DMESG**)malloc( ringSize * sizeof(DMESG*));

//set to null, it's being checked before putting stuff in
//to make sure the existing msg gets cleaned.
memset(pdmesgRing->pDmesgArray, 0, ringSize * sizeof(PDMESG));
if ( ! pdmesgRing->pDmesgArray ){
goto ErrorExit;
}

// Init the ring's queued spinlock
//KeInitializeSpinLock(&pdmesgRing->queuedSpinLock);
//tie it with global ring pointer
g_pDmesgRing = pdmesgRing;

return pdmesgRing;

ErrorExit: //coming here => error

if (pdmesgRing->pDmesgArray ){
free(pdmesgRing->pDmesgArray );
}

if (pdmesgRing){
free(pdmesgRing );
}

return NULL;
}


VOID
AddmesgToRing (DMESG_LVL verbosity, CHAR * mesg)
{
PDMESG pdmesg;

//KLOCK_QUEUE_HANDLE lockHandle;
//NTSTATUS ntStatus;
size_t countByte;

//first check for existing element in the ring
if (g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]){
pdmesg = g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx];
if (pdmesg->msg){
free ( pdmesg->msg);
}

}else{ //create a new
g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]= (PDMESG)malloc( sizeof(DMESG));
}

if ( !g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]) {
goto ErrorExit;
}

countByte = strlen(mesg);

//init the msg entry
g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]->msglen = countByte;
g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]->lvl = verbosity;
g_pDmesgRing->pDmesgArray[g_pDmesgRing->producerIdx]->msg = mesg;

//Acquire lock
//KeAcquireInStackQueuedSpinLock(&g_pDmesgRing->queuedSpinLock, &lockHandle);
g_pDmesgRing->producerIdx++;
g_pDmesgRing->producerIdx %= g_pDmesgRing->ringSize;
//KeReleaseInStackQueuedSpinLock(&lockHandle);
//release lock
return;
ErrorExit:
if (pdmesg){
free(pdmesg);
}
}

#define NUM_RING_ELEMENTS 2
void freeAll()
{
PDMESG pdmesg;
int i;
for ( i =0; i < NUM_RING_ELEMENTS; i++){

pdmesg = g_pDmesgRing->pDmesgArray[i];
free(pdmesg->msg);
pdmesg->msg = 0;
free(pdmesg);

}

for ( i =0; i < NUM_RING_ELEMENTS; i++){
free(*g_pDmesgRing->pDmesgArray + i);
}

free (g_pDmesgRing);
}

void main()
{
//char msgs[512];
char *buf;
int i;
AllocdmesgRing( NUM_RING_ELEMENTS );
for ( i =0; i < 3 ; i++){
buf = (char*)malloc(SIZE_DMESG );
memset(buf, 'a'+i, SIZE_DMESG);
buf[SIZE_DMESG -1] = '\0';
AddmesgToRing( DMESG_VERBOSE, buf );
}

for (i =0; i < NUM_RING_ELEMENTS; i++){
PDMESG pdmesg;
pdmesg = g_pDmesgRing->pDmesgArray[i];
printf("lvl=%d Verbosity=%d, msg=%s\n", pdmesg->lvl, pdmesg->msglen,pdmesg->msg);

}
freeAll();


}

 

 

 

 

 

 

Posted on Monday, May 27, 2013 at 08:49AM by Registered CommenterProkash Sinha | Comments Off

Communicating Processes II

I do know how important it is to have a proper communication, as I said earlier. Most people learn to have a persuasive and intelligent communication that results in achieving objetives. But in computer communications between communicating processes, there is hardly any room for being persuasive, or rather persuasive means correct.

In my previous note, I mentioned how shared memory can be used for interprocess communications, but all the synchronization will be needed to achive correct communication. And it is something that can be delegated to the underlying systems by using other methods. In windows, one such method is to use named pipe. It is FIFO, and bit more.

The objective of my experiment was to have send and receive loop between server and multiple applications (client) that are to communicate with the server. Essentially, the server will have a dedicate pair of channels between a specific client and itself. So if 10 clients try to communicate with the server, there will be 10 pairs of IPC channels. Each pair has two unidirectional channels going in each direction. The choice of having a pair of unidirectional channel instead of one bidirectional channel is to simplify the implementation and debugging. By nature, an application gets a handle to an opened instance from the system, and that's it. Now to make a sane channel, you and I will have to wrap this as an element of an abstract channel. The abstract channel can have lots of additional information like: state, message received or sent, last used time so on and so forth. Now the channels are really cross-bar switch. The read-end of one is the write-end of the partner and vice versa.

I started out with such abstract channel, just because I knew that for debugging and performances I would be needing these. One problem, and it is always the problem when communicating processes are to have a sustained communication is  - THE DEADLOCK. This is mainly due to foreseeing the flaws in assumptions.

My assumption was that if (1) send and receives are blocking call (2) If they starts in alternating ( i.e. ping-pong) fashion (3) IPC channel is flawless, then I don't need any synchronization. Theoritically this is true. We can argue by stepping thru the scenarios that satisfies the above assumptions and show that there does not need any synchronization...

Now since I implemented the IPC, how could I prove the channels are somewhat ( if not totally) flawless. This is the reason I started out with the abstract channel. But assumption (1) was not true. Blocking here is from the local system point of view, it is not blocking or synchrous with respect to the other end. The assumption was that the call will be blocked until the local end-point knows how to satisfy the call. The end-point is the end-point of the channel instance. 

 

The problem is that, if you just try to use the above assumption, and try out IPC as stated, it would work. In my case I was testing some of my own software, that does not necessarily send the message to the local end of the IPC channel, depending on the load of the system. Hence making send side essentially asynchrous. Correct implementation will have a pending queue with associative aging algorithm to get it off the queue and send it, then we would not see the deadlock in ping-pong style communication. But that was the side-effect, in a good way, to find the bug out to see why it was deadlocking...

 

Net result of this note, is that as long as the asumptions (persuasiveness ) are clearly understood, communication is fun, otherwise big challenges to find flaws in assumption(s).

 

Posted on Wednesday, November 21, 2012 at 06:04PM by Registered CommenterProkash Sinha | CommentsPost a Comment

Communicating Processes

Really, I'm strong believer of communication. Actually in every form, be it written, spoken, sign and signals. It is really the input of all facet of learning. And who does not want to learn?

Communicating Processes means two or more processes will communicate among them. Simple example of it is two processes communicating with each other. And the media is of course information bus. This information bus could be almost anything. Processes talks over wireless, wired networks, over physical media other than what we call network today. The most fundamental aspect of communication is - Signal processing. This is in the physics and engineering domain. But our topic here is digital communication. Particularly, using Windows systems.

 Usually the steps to achieve a good / effective / reliable communication, the following steps are important -

 

  • Choose the infromation Bus: Network, Physical Media, storage systems etc.
  • Get a way to programmatically Talk: It is to transmit junk back and forth to see the bus is active and raw.
  • Devise protocol(s) to have good / effective / reliable communications
  • Incrementally implement.
  • Test & Debug.

 

In order to achieve a quick ( Well, fairly quick I would say ! ) implementation, I took the simplest approach first. It is the shared memory technique in user level programming. In a hurry, I will have few bad pointer references, and user level would save lot of pain and agony if you understand what I mean. Now shared memory is thru file mapped paradigm in Windows system. So the information Bus I selected is shared memory.

In order to make things simple, I picked a pair of such information bus, each in one direction. Here we can have a choice to communicate from one end to other what bus would be used in which direction or we can have an apriori assumption about which bus would take what direction. For shared memory, I just took the apriori assumption by giving explict name like: client shared memory, server shared memory. The naming is purely based on who would be using the bus for writing information to the bus. So Server shared memory information bus is for server to write and client to read. Things are simple. Why? Because by the time client or server starts, everything about the bus is already in place. The just blindly need to communicate with each other, just like the way we talk and never thought of the atomosphare ( particularly eather ) that acts as a bus.

 

Once the bus is in place and in raw mode, we can talk - no matter how nonsensical they are :). This is to see information is getting exchanged. Albiet, both side having bad experiences in learing, if anything since it is like talking rubbish, and no communication at all.

Now the next step is to carry the payload across with meaningful context. Remember in older days, when we had very noisy telecom line for long distance trunk system and we use to loose context and used asked for what what, please repeat etc.

So this meaningful contex is really the protocol. In this particular protocol we had the following -

1) A payload would be processed only once by the destination since that payload was conveyed only once.

2) The payload with associated protocol information is called message. Each message is atomically processed.

3) Every message has to be processed.

 

Now since a message is processed only once, consumption of the message means it is gone from the pipe once processed. In our case the reader will atomically read, and if it is indeed a message from writer, it will atomically erase. On the writer side, it will make sure that the pipe/bus has no message ( it is single message channel) and atomically write the whole message.

The payload is wrapped with hdr informations that indicates say: client id, sequence number, message length etc. The message itself is within the total payload.

Following these simple rules, it is fairly easy to cookup a base line information bus for communicating processes.

Enjoy!

-pro

Posted on Wednesday, October 24, 2012 at 07:41PM by Registered CommenterProkash Sinha | CommentsPost a Comment
Page | 1 | 2 | 3 | 4 | 5 | Next 5 Entries