Method and apparatus using a tree structure for the dispatching of interrupts

• US 5,568,644 A
• Filed: 05/05/1995
• Issued: 10/22/1996
• Est. Priority Date: 05/05/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Saulpaugh, Thomas E., Nelson, Matthew R.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Seto, Jeffrey K.
• Application Number:
  US08/435,967
• Time in Patent Office: 536 Days
• Field of Search: 395/800, 395/732, 395/741, 395/733, 395/742
• US Class Current: 710/268
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked

Abstract

Each device is represented by a node in a hierarchical tree, referred to herein as an interrupt source tree (IST). The root and intermediate nodes of the IST represent dispatching or determining points; this removes the need for the device drivers to contain dispatching code; the drivers now only need to contain interrupt handling code specific to the device itself. At these nodes code is executed to determine which branch to take down the IST. The bottom nodes are the leaf nodes; the leaf nodes identify the device interrupt handler. By moving the determination steps performed by the different device drivers to the nodes of the IST, the device drivers are modular and portable. Furthermore, changes to the computer system configuration, which in the prior art would require modification of all device drivers, can be adapted to by modification of the IST.

Claims

1. In a computer system comprising a processor and a plurality of devices coupled to a bus, an interrupt dispatching apparatus for determining an interrupt source from the plurality of devices that issued an interrupt request to the processor, said interrupt dispatching apparatus comprising:

an interrupt source tree (IST) comprising a plurality of hierarchically arranged nodes, said nodes comprising a root node and a plurality of leaf nodes connected to higher level nodes in the hierarchy through branches, said root node providing a branch direction to at least one leaf node, at least one of said leaf nodes comprising an identification of an interrupt source;

an interrupt dispatcher, responsive to an interrupt from an interrupt source, traversing said IST by invoking a routine pointed to by said root node to determine a branch direction to one of said plurality of leaf nodes, said one of said plurality of leaf nodes identifying said interrupt source.

2. An apparatus for servicing interrupt requests in a computer system, the apparatus comprising an interrupt source tree (IST) comprising a plurality of hierarchically arranged nodes including a plurality of leaf nodes, the plurality of leaf nodes identifying at least one interrupt handler.

3. The apparatus of claim 2 wherein at least one of said plurality of nodes points to a transversal routine for execution, the transversal routine, when executed, indicating a branch direction.

4. The apparatus of claim 2 wherein at least one of said plurality of nodes points to an interrupt disable routine (IDR) for execution, the IDR, when executed, disabling execution of the interrupt handler.

5. The apparatus of claim 2 wherein at least one of said plurality of nodes points to an interrupt enable routine (IER) for execution, the IER, when executed, enabling execution of the interrupt handler.

6. The apparatus of claim 2 wherein at least one of said plurality of nodes points to an interrupt acknowledge routine (IAR) for execution, the IAR, when executed, acknowledging an interrupt service request from a requesting device.

7. A method for servicing interrupt requests in a computer system, the method comprising the computer-implemented steps of:

generating an interrupt source tree (IST) comprising a plurality of hierarchically arranged nodes; and

responsive to an interrupt request, traversing the IST to locate an interrupt handler pointed to by one of the plurality of nodes.

8. The method of claim 7 further comprising the step of traversing the IST in a reverse direction to determine if another interrupt request has been asserted.

9. The method of claim 7 wherein said step of traversing the IST to locate an interrupt handler comprises the steps of:

(a) setting one of the plurality of nodes comprised by the IST to be a current evaluation node;

(b) executing a routine pointed to by the current evaluation node, the routine generating a value;

(c) if the value identifies a child node of the current evaluation node, setting the child node to be the current evaluation node; and

(d) repeating steps (b) through (c) until the value indicates that the interrupt handler has been located.

10. The method of claim 9 wherein said step of setting one of the plurality of nodes to be a current evaluation node comprises an initial step of setting a root node of the plurality of nodes to be the current evaluation node.

11. A method for controlling interrupt service in a computer system, the method comprising the steps of:

generating an interrupt source tree (IST) comprising a plurality of nodes hierarchically arranged to be traversed to locate and execute an interrupt handler pointed to by a leaf node of the plurality of nodes; and

executing an interrupt disable routine (IDR) pointed to by the plurality of nodes to disable execution of the interrupt handler.

12. The method of claim 11 wherein said step of executing an IDR pointed to by the plurality of nodes comprises the step of executing an IDR pointed to by the leaf node.

13. The method of claim 11 further comprising the step of executing an interrupt enable routine (IER) pointed to by the leaf node to enable execution of the interrupt handler.

14. The method of claim 11 wherein said step of executing an IDR pointed to by the plurality of nodes comprises the step of executing an IDR pointed to by a first node of the plurality of nodes to disable traversal of the first node to reach a node of the IST on a branch extending from the first node to the leaf node.

15. The method of claim 14 further comprising the step of executing an interrupt enable routine (IER) pointed to by the first node to enable traversal of the first node to reach the leaf node.

16. The method of claim 15 wherein said step of executing an IER pointed to by the first node comprises the step of enabling traversal of at least one node of the IST hierarchically higher than the first node.

17. The method of claim 16 wherein said step of enabling traversal of at least one node of the IST hierarchically higher than the first node comprises the steps of:

traversing the IST from the first node to a hierarchically higher node of the plurality of nodes; and

executing an IER pointed to by the hierarchically higher node.

18. The method of claim 14 further comprising the step of executing an interrupt enable routine (IER) pointed to by a second node of the plurality of nodes to enable traversal of the first node to reach the leaf node, the second node being on the branch extending from the first node to the leaf node.

19. The method of claim 14 further comprising the step of executing an interrupt enable routine (IER) pointed to by the leaf node to enable traversal of nodes of the IST hierarchically higher than the leaf node to reach the leaf node.

20. A method for servicing interrupt requests in a computer system, the method comprising the computer-implemented steps of:

(a) generating an interrupt source tree (IST) comprising a hierarchical structure of nodes including a root node and a plurality of leaf nodes connected to the root node via branches;

(b) traversing the IST from the root node of the IST to a first leaf node of the IST in response to a first interrupt request; and

(c) executing an interrupt handler pointed to by the first leaf node to service the first interrupt request.

21. The method of claim 20 wherein said step of traversing an IST from a root node to a first leaf node comprises the steps of:

(b1) setting the root node to be a current evaluation node;

(b2) executing a transversal routine pointed to by the current evaluation node, the transversal routine generating a value;

(b3) if the value identifies a child node of the current evaluation node, setting the child node to be the current evaluation node; and

(b4) if the value identifies a child node of the current evaluation node, repeating steps (b2) through (b3).

22. The method of claim 21 wherein said step of executing a transversal routine comprises the step of preventing successive servicing of interrupt requests generated by a first device during an interval in which a second device generates an interrupt request.

23. The method of claim 20 wherein after said step of (c) executing an interrupt handler, the method further comprises the steps of:

(d) setting a parent node of the current evaluation node to be the current evaluation node;

(e) executing a transversal routine pointed to by the current evaluation node; and

(f) repeating steps (d) through (e) until the transversal routine identifies a child node of the current evaluation node or until the current evaluation node is the root node.

24. The method of claim 23 further comprising the step of:

(g) if the transversal routine identifies a child node of the current evaluation node, performing the following steps;

(g1) traversing the IST from the current evaluation node to a second leaf node, the child node being on a branch of the IST comprising the second leaf node; and

(g2) executing an interrupt handler pointed to by the second leaf node.

25. The method of claim 20 wherein after said step of (c) executing an interrupt handler, the method further comprises the steps of:

(d) if the current evaluation node comprises a modifying option, setting a node of the IST identified by the modifying option to be the current evaluation node;

(e) if the current evaluation node does not comprise a modifying option, setting a parent node of the current evaluation node to be the current evaluation node;

(f) executing a transversal routine pointed to by the current evaluation node; and

(g) repeating steps (d) through (f) until the transversal routine identifies a child node of the current evaluation node or until the current evaluation node is the root node.

26. The method of claim 25 further comprising the step of:

(h) if the transversal routine identifies a child node of the current evaluation node, performing the following steps;

(h1) traversing the IST from the current evaluation node to a second leaf node, the child node being on a branch of the IST comprising the second leaf node; and

(h2) executing an interrupt handler pointed to by the second leaf node.

27. A method for servicing interrupt requests in a computer system, the method comprising the steps of:

(a) generating an interrupt source tree (IST) comprising a plurality of nodes;

(b) setting a root node of the plurality of nodes to be a current evaluation node;

(c) executing a routine pointed to by the current evaluation node, the routine generating a value;

(d) if the value identifies a child node of the current evaluation node, setting the child node to be the current evaluation node;

(e) repeating steps (c) through (d) until the value does not identify a child node of the current evaluation node;

(f) if the value indicates that an interrupt handler has executed, but an interrupt request has not been serviced, and if the current evaluation node is not the root node, repeating the following steps until the current evaluation node is the root node or until the value indicates that an interrupt request has been serviced;

(f1) determining whether the parent node of the current evaluation node is to be reevaluated;

(f2) if the parent node of the current evaluation node is to be reevaluated, performing the following steps;

(f2a) setting a parent node of the current evaluation node to be the current evaluation node;

(f2b) repeating steps (c) through (f);

(f3) if the parent node of the current evaluation node is not to be reevaluated, and if another child node of a set of child nodes comprising the current evaluation node has not been set to be the current evaluation node, performing the following steps;

(f3a) setting the other child node to be the current evaluation node;

(f3b) repeating steps (c) through (f);

(f4) if the parent node of the current evaluation node is not to be reevaluated, and if each child node of the set of child nodes comprising the current evaluation node has been set to be the current evaluation node, setting a parent node of the current evaluation node to be the current evaluation node;

(g) if the value indicates that an interrupt handler has serviced an interrupt request, and if the current evaluation node is not a root node of the IST, repeating the following steps until the current evaluation node is the root node;

(g1) setting the parent node of the current evaluation node to be the current evaluation node;

(g2) determining whether the parent node of the current evaluation node is to be reevaluated; and

(g3) if the parent node of the current evaluation node is to be reevaluated, repeating steps (c) through (g).

28. The method of claim 27 wherein said step (f1) of determining whether the parent node of the current evaluation node is to be reevaluated comprises the step of examining the current evaluation node.