Kernel functions for inter-processor communications in high performance multi-processor systems

• US 7,873,964 B2
• Filed: 10/30/2006
• Issued: 01/18/2011
• Est. Priority Date: 10/30/2006
• Status: Expired due to Fees

• Current Assignee: III Holdings 1, LLC, Liquid Computing Corporation
• Original Assignee: Liquid Computing Corporation
• Inventors: Munter, Ernst, Kemp, Michael F., Narayanan, Damodharan, Huang, Kaiyuan, Bathala, Venkatesh
• Primary Examiner(s): Cao; Diem K
• Application Number:
  US11/554,535
• Publication Number:
  US 20080148291A1
• Time in Patent Office: 1,541 Days
• Field of Search: 719/314
• US Class Current: 719/314
• CPC Class Codes: G06F 9/545 where tasks reside in different layers, e.g. user- and kernel-space

Abstract

In a multi-processor system with a high degree of inter processor communication, an operating system extension is described as a kernel function to poll a receive buffer. This is an opportunistic poll that continues to run in the user context after an application process has invoked the kernel with a blocking receive function. It is also running whenever no higher priority task is running. New data packets may be received for the present user application process while avoiding context switches, and for a different user process while avoiding interrupts. A hardware implemented delay timer and a buffer fill monitor generate interrupts when the system is not polling, thus guaranteeing a maximum latency and preventing buffer overflow, but these interrupts are largely avoided by polling when the system is handling a large amount of inter processor data traffic.

Claims

1. A method for operating a computer, the computer having a multi-tasking operating system that includes a user space and a kernel in a kernel space, a receive buffer and a plurality of application processes, each of the plurality of application processes including a user application that runs in the user space, the method comprising the steps of:

polling the receive buffer from a user polling function that runs in the kernel space;

receiving in the receive buffer a data packet having a header and user data;

reading the header of the received data packet;

identifying a target application process of the plurality of application processes from the read header;

delivering the user data to the identified target application process, and

if the identified target application process is in a blocked state, changing the blocked target application process to an unblocked state;

wherein the polling step is carried out by a polling application process that includes the user polling function.

2. The method of claim 1, wherein each of the plurality of application processes is associated with a process context and wherein the method further includes a step of discarding the data packet if the process context of the target application process does not exist.

3. The method of claim 1, wherein the target application process in the delivering step is one of a polling application process and a non-polling application process that does not include the user polling function.

4. The method of claim 1, wherein the polling step is carried out as long as the receive buffer is empty and no other application process is ready to run.

5. The method of claim 1, further comprising the step of each of the plurality of application processes assuming the blocked state when it is waiting for user data.

6. The method of claim 1, wherein, after the polling step is carried out by a first user polling function of a first application process of the plurality of application processes and after the identifying step identifies the target application process as a second one of the plurality of application processes, the method further includes a step of the first application process assuming the blocked state.

7. The method of claim 1, wherein the polling step is carried out such that after a first application process of the plurality of application processes issues a blocking receive call to indicate that it is ready to receive data, the polling step is carried out to poll the receive buffer and the method further includes a step of copying the user data from the receive buffer to the user space of the first application process if the identified target application process is the first application process.

8. The method of claim 1, further including a step of each of the plurality of application processes assuming the blocked state after its associated user application issues a blocking receive call to the kernel indicating that the issuing user application is waiting for data and the identifying step identifies the target application process as being an other one of the plurality of application processes.

9. The method of claim 8, wherein the kernel further carries out a step of changing the other one of the plurality of application processes to the unblocked state to enable the unblocked user application to receive and process the user data of the data packet received in the receive buffer.

10. The method of claim 1 wherein, when the identified target application process is not yet waiting for the data packet received in the receive buffer, the method further includes a step of the kernel sending the user data to a queue from which the identified target application process can remove the user data after having issued a blocking receive call to indicate to the kernel that it is waiting for data, but before the identified target application process assumes the blocked state.

11. The method of claim 1, further including a step of generating a receive buffer interrupt signal after a selectable period of time, the selectable period of time being configured to be started each time a new data packet arrives at an input of the receive buffer, unless the selectable period of time has at least already partially elapsed.

12. The method of claim 11, further including a step of clearing the selectable period of time when the polling step is carried out.

13. The method of claim 11, further including a step of programmatically setting the selectable period of time.

14. The method of claim 1, further including steps of monitoring a fill level of the receive buffer, and generating a receive buffer fill interrupt signal when the receive buffer fills to a selectable fill level.

15. The method of claim 1, wherein the kernel includes a kernel polling thread, and wherein the method further includes a step of the kernel polling thread polling the receive buffer when none of the plurality of application processes are running or are ready to run.

16. The method of claim 15, wherein the kernel polling thread polling step is carried out persistently, yielding and suspending execution only temporarily when one of the plurality of application processes is ready to run.

17. The method of claim 15 wherein, after the kernel polling thread polling step, the method further includes steps of, when a data packet is present in the receive buffer, reading the header of the data packet, identifying the target application process for the user data from the read header, delivering the user data to the identified target application process and changing the state of the target application process to the unblocked state if the target application process is in the blocked state.

18. A computer, comprising:

a multi-tasking operating system having a user space and a kernel in a kernel space;

a receive buffer, configured to receive a data packet having a header and user data;

a plurality of application processes, each of the plurality of application processes including a user application that runs in the user space, at least one of the plurality of application processes being polling application processes that also include a user polling function that runs in the kernel space, each of the plurality of application process being configured to assume an unblocked or a blocked state, the user polling function being configured to poll the receive buffer and, when a data packet is present in the receive buffer, to read the header of the data packet, to identify a target application process for the data packet from the read header, to deliver the user data to the identified target application process and to change a state of the target application process to the unblocked state if the target application process is in the blocked state.

19. The computer of claim 18, wherein each of the plurality of application processes is associated with a process context and wherein the kernel is further configured to discard the data packet if the process context of the target application process does not exist.

20. The computer of claim 18, wherein the user polling function is configured to poll the receive buffer as long as the receive buffer is empty and no other application process is ready to run.

21. The computer of claim 18, wherein each of the plurality of application processes is configured to assume the blocked state when waiting for user data.

22. The computer of claim 18, wherein the user polling function of each of the at least one polling application process is configured to cause its application process to assume the blocked state when the target application process is identified as a application process of the plurality of application processes other than itself.

23. The computer of claim 18, wherein the user polling function of each of the at least one polling application process is configured such that after a first polling application process makes a blocking receive call to the kernel to indicate that it is ready to receive data, but before the first polling application process assumes the blocked state, the user polling function polls the receive buffer and copies the user data from the receive buffer to the user space of the first polling application process if the identified target application process is the first polling application process.

24. The computer of claim 18, wherein each of the plurality of application processes is configured to assume the blocked state after making a blocking receive call to the kernel indicating that the issuing user application is waiting for data and a new data packet for an other one of the plurality of application processes is received in the receive buffer.

25. The computer of claim 24, wherein the kernel is configured to change the other one of the plurality of application processes to the unblocked state to enable the user application of the unblocked application process to receive and process of the user data received in the receive buffer.

26. The computer of claim 18 wherein, when the identified target application process is not yet waiting for the user data in the data packet received in the receive buffer, the kernel is configured to send the user data to a queue from which the identified target application process can remove the user data after having issued a receive blocking call to indicate to the kernel that it is waiting for data, but before the identified target application process assumes the blocked state.

27. The computer of claim 18, further including a delay timer that is configured to generate a receive buffer delay interrupt signal after a selectable period of time, the delay timer being configured to be started each time a new data packet arrives at an input of the receive buffer, unless the selectable period of time has at least already partially elapsed.

28. The computer of claim 27, wherein the delay timer is configured to be cleared when the user polling function reads the header of the data packet from the receive buffer.

29. The computer of claim 28, wherein the selectable period of time is programmatically selectable.

30. The computer of claim 28, further including a fill level monitor coupled to the receive buffer, the fill level monitor being configured to monitor a fill level of the receive buffer and to generate a receive buffer fill interrupt signal when a selectable receive buffer fill level is reached.

31. The computer of claim 18, wherein the kernel further includes a kernel polling thread that is configured to poll the receive buffer when none of the plurality of application processes are running or are ready to run.

32. The computer of claim 31, wherein the kernel polling thread is configured to run persistently, yielding and suspending execution only temporarily when one of the plurality of application processes is ready to run.

33. The computer of claim 31, wherein the kernel polling thread is configured to poll the receive buffer and, when a data packet is present in the receive buffer, to read the header of the data packet, to identify a target application process for the user data from the read header, to deliver the user data to the identified target application process, and to change the state of the target application process to the unblocked state if the target application process is in the blocked state.