text:
US10007592B2 - Debugging non-deterministic embedded systems - Google PatentsDebugging non-deterministic embedded systems Download PDF
- Publication number
- Authority
- United States
- Prior art keywords
- data
- instructions
- ndr
- processor
- register
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active, expires
- 238000004590 computer program Methods 0.000 claims abstract description 63
- 238000007906 compression Methods 0.000 claims abstract description 62
- 239000002609 media Substances 0.000 claims abstract description 58
- 230000015654 memory Effects 0.000 claims abstract description 45
- 230000000875 corresponding Effects 0.000 claims abstract description 23
- 230000002093 peripheral Effects 0.000 claims description 61
- 238000000034 methods Methods 0.000 claims description 37
- 230000000694 effects Effects 0.000 description 8
- 230000006399 behavior Effects 0.000 description 6
- 230000000051 modifying Effects 0.000 description 3
- 230000004044 response Effects 0.000 description 3
- 238000005265 energy consumption Methods 0.000 description 2
- 238000005516 engineering processes Methods 0.000 description 2
- 238000004458 analytical methods Methods 0.000 description 1
- 230000002085 persistent Effects 0.000 description 1
- 239000000126 substances Substances 0.000 description 1
- 230000002123 temporal effects Effects 0.000 description 1
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Preventing errors by testing or debugging software
- G06F11/362—Software debugging
- G06F11/366—Software debugging using diagnostics
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Preventing errors by testing or debugging software
- G06F11/362—Software debugging
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Preventing errors by testing or debugging software
- G06F11/362—Software debugging
- G06F11/3636—Software debugging by tracing the execution of the program
- G06F11/364—Software debugging by tracing the execution of the program tracing values on a bus
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/30098—Register arrangements
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline, look ahead
- G06F9/3861—Recovery, e.g. branch miss-prediction, exception handling
- G06F9/3865—Recovery, e.g. branch miss-prediction, exception handling using deferred exception handling, e.g. exception flags
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/60—General implementation details not specific to a particular type of compression
This application is a 35 USC § 371 filing of International Application No. PCT/US2014/058999, filed Oct. 3, 2014, and entitled "Debugging Non-Deterministic Embedded Systems," which claims priority to and the benefit of U.S. Provisional Patent Application Ser. No. 61/893,923, filed Oct. 22, 2013, and entitled "System-Level Record and Replay in Wireless Sensor Networks," the entirety of which is incorporated herein by reference.
This invention was made with government support under CNS-0834529 and ECCS-0925851 awarded by the National Science Foundation. The government has certain rights in the invention.
The present disclosure generally relates to software-trace and software-replay systems, and in particular to such systems used in debugging tools for embedded computing devices.
Networks of computing devices are used in many applications. One such example is a wireless sensor network (WSN) that includes a large number of nodes that are in remote communication with a base station. These nodes communicate data with the base station, on a regular or irregular basis. In either case, the data can be communicated with deterministic or non-deterministic timing. In the event the network behaves in a manner that is unexpected, e.g., when a bug occurs, determining the source of the bug can be challenging due to, e.g., remoteness of deployed sensor nodes (e.g., inaccessibility), the non-deterministic nature of data or of a sequence of execution that can make it challenging to replicate the bug, or the limited hardware resources available on a node.
A mechanism for debugging such networks is known as "record and replay," which logs a trace of predefined events while an application is executing such that the events can be replayed later using associated debugging tools. However, these debugging tools have various limitations. For example, existing recording methods for WSNs for several reasons cannot capture complete code execution associated with the nodes, thus resulting in the inability to effectively replay and thereby causing some bugs to go unnoticed. For example, prior deterministic record and replay methods cannot adequately trace non-deterministic events such as sensor values or message arrival times, and do not execute efficiently on limited-resource computing nodes.
According to an aspect, there is provided an embedded device comprising: a processor; a nonvolatile computer storage medium; a code memory; and one or more module(s) stored in the code memory and configured for execution by the processor, the one or more module(s) including instructions to: read data from a first non-deterministic register (NDR) of a first type; read data from a second, different NDR of a second, different type; compress the data from the first NDR using a first compression algorithm to provide first compressed data; compress the data from the second NDR using a second, different compression algorithm to provide second compressed data; and store the first and second compressed data in the nonvolatile medium.
According to another aspect, there is provided a method of enabling debug tracing in a computer program product, the computer program product comprising instructions for use within an architecture of an embedded device, the method including: locating one(s) of the instructions that read an NDR, the locating being performed using register data of the architecture; determining a register type of the NDR using the register data; adding instruction(s) to the computer program product following the located instruction(s), the added instruction(s) including instruction(s) for use within the architecture to compress the value read by the located instruction(s) using a compression algorithm corresponding to the determined register type; and repeating the locating, determining, and adding steps for each of a plurality of located one(s) of the instructions of the computer program product using compression algorithms corresponding to the respective determined register types.
According to yet another aspect, there is provided a computer program product comprising a computer readable medium and an emulator computer program mechanism embedded therein, the emulator computer program mechanism comprising instructions for: receiving emulation-target instructions and compressed data of NDR values, wherein the emulation-target instructions include first instructions to read NDRs and second instructions; emulating an execution sequence of the emulation-target instructions, the emulating including: for each second instruction in the execution sequence, updating an emulated-machine state based on that second instruction; and for each first instruction in the execution sequence: determining a type of the NDR read by the first instruction; decompressing a portion of the compressed data using a decompression algorithm corresponding to the determined register type; and updating the emulated-machine state based on the decompressed portion.
Various aspects advantageously permit tracing of longer, broader traces than prior schemes. Various aspects advantageously permit debugging a wider range of bugs than do prior schemes.
The above and other objects, features, and advantages of the present application will become more apparent when taken in conjunction with the following description and drawings wherein identical reference numerals have been used, where possible, to designate identical features that are common to the figures, and wherein:
The attached drawings are for purposes of illustration and are not necessarily to scale.
For the purposes of promoting an understanding of the principles of the present disclosure, reference will now be made to the embodiments illustrated in the drawings, and specific language will be used to describe the same. It will nevertheless be understood that no limitation of the scope of this disclosure is thereby intended.
In the description below, some aspects will be described in terms that would ordinarily be implemented as software programs. Those skilled in the art will readily recognize that the equivalent of such software can also be constructed in hardware, firmware, or micro-code. Because data manipulation algorithms and systems are well known, the present description will be directed in particular to algorithms and systems forming part of, or cooperating more directly with, systems and methods described herein. Other aspects of such algorithms and systems, and hardware or software for producing and otherwise processing the signals involved therewith, not specifically shown or described herein, are selected from such systems, algorithms, components, and elements known in the art. Given the systems and methods as described herein, software not specifically shown, suggested, or described herein that is useful for implementation of any aspect is conventional and within the ordinary skill in such arts. Various aspects described herein may be embodied as systems or methods. Accordingly, various aspects herein may take the form of an entirely hardware aspect, an entirely software aspect (including firmware, resident software, micro-code, etc.), or an aspect combining software and hardware aspects These aspects can all generally be referred to herein as a "service," "circuit," "circuitry," "module," or "system."
"Non-determinism" and similar terms refer to influences on the behavior of a computing device that are outside the control of that computing device or processor(s) therein. For example, sensor values are non-deterministic (from the viewpoint of the software on a computing device), since their values are not known or determinable from any characteristics of the software. Values read on I/O ports or addresses (in systems using memory-mapped I/O) are non-deterministic. Accordingly, the behavior of a computing device in response to non-deterministic values is also non-deterministic.
There is a need for a novel real-time debugging system capable of recording and replaying data associated with nodes in a network of plurality of nodes, where such nodes execute software using non-deterministic data. There is a need for ways of replaying the chain of events leading up to a software failure so bugs can be located and fixed.
Prior work used custom field-programmable gate arrays (FPGAs) to assist record and reply replay. Various aspects herein advantageously use software running on stock processors and do not require hardware changes to nodes under test. In various aspects, record and replay can be performed without the support of a virtualization environment such as VMware. Various aspects advantageously permit recreating the same memory state during debugging as existed at runtime, enabling software testers or developers to use a much wider range of debugging tools than do prior schemes.
In the present disclosure a trace and replay debugging system for, e.g., sensor nets or other networks of embedded devices, or other computing devices (hereinafter referred to as TARDIS) is presented. TARDIS is configured for record and re-play of data associated with nodes in a network, e.g., wireless sensor network (WSN) nodes. The system described herein is applicable to a broad area of resource constrained embedded systems. TARDIS may be configured to record substantially all sources of non-determinism, and can compress data that is to be recorded using domain-specific compression techniques.
Debugging is often performed in a cyclic process of repeatedly executing a program and tracking down bugs. In WSNs, cyclic debugging can be a time consuming and laborious task. Programmers of WSNs often use tools such as simulators, safe code enforcement, and formal testing prior to deployment of the application in the field. However, the reality is that exhaustive testing of all or even substantially all conditions in a pre-deployment setting, e.g., in a laboratory, may not be feasible because WSNs are typically deployed in throughput-challenged environments whose behavior cannot be easily duplicated in a laboratory. When a bug manifests itself in a deployed WSN, detecting and diagnosing the bug can thus be a daunting task. Nodes are often not easily physically accessible, meaning that the programmer must rely on low-power wireless links to collect any data of interest. There may not be sufficient information available to immediately diagnose a bug, so the network must be wirelessly reprogrammed to collect additional debugging data. This iterative process can be time consuming. Once a bug fix is applied, the network is again wirelessly reprogrammed, and further monitoring is required to determine that the bug has been successfully fixed. The cyclic debugging approach of fix and test becomes particularly laborious in this environment.
Record and replay can make the process of cyclic debugging less tedious. Record and replay is a debugging technique where program execution is recorded in real-time and then reproduced off-line. Record and replay cuts down on the cyclic process of debugging by capturing a program's execution such that it can be deterministically reproduced and carefully examined off-line, for identifying a bug. It is a particularly valuable technique for WSNs, because the recording can happen on the nodes and the replay and debugging can happen on the relatively resource rich desktop-class machines, e.g., at a base station. The typical workflow for record and replay in WSNs is that during normal execution of a deployed WSN, the nodes execute instrumented binaries that record a trace of all sources of non-determinism to Flash. The trace can then be brought back to the lab for offline replay. This can be done either through wireless data collection or by physically accessing a node. In the lab, the recorded data is fed into an emulator, which replays the node's execution. The replay allows a developer to examine the program's execution, including its interactions with the environment, at various arbitrary levels of detail, such as through setting breakpoints or querying the state of memory. Such replay helps the developer identify the root cause of bugs encountered in the field.
The main processor and non-volatile storage are often heavily constrained in WSNs, in order to reduce cost, size, and energy consumption of individual nodes. The main processor is typically a microcontroller (processor) which may be limited to a few MHz clock speed, and random access memory (RAM) in the range of tens of kilobytes. Non-volatile storage is usually a Flash chip which may contain anywhere from MB to a few GB of storage. In one exemplary embodiment, a WSN sensor node has 1 MB of Flash and 2 GB SD card for storage. However, trace data rates of 5.4 MB per minute are typical in some WSN type applications. Additionally, storing data to Flash is energy intensive, with frequent Flash usage reducing a node's battery lifetime by, e.g., a factor of 3.
Moreover, WSNs often have soft real-time constraints. Adding instrumentation to record non-deterministic events can interfere with the timing of the main application and associated tasks causing excessive delays in the allotted cycles. In an example, each sensing cycle of a node in a WSN is only allotted 2 s.
WSNs often do not have a clear separation between application and system software. Some WSN nodes operate without an operating system (in a "bare-metal" configuration). For example, there is typically no hardware memory protection on most low-end processors, and prominent WSN operating systems (OSes), e.g., open-source OSes designed for low-power wireless devices, such sensor networks, personal area networks, smart buildings and smart meters. As a result, logging only application events can be insufficient in some systems, since the application can affect the behavior or functioning of the operating system. This contributes to a need in some systems to also log operating-system events in a trace, which increases the memory required for the trace. It can be desirable to record the complete execution of a sensor node's processor for replay, rather than only application components. This record and replay is referred to as system-level, which is more resource intensive than application-level record and replay.
In WSNs, it is sometimes impracticable to record every instruction (due to resource and real-time constraints). Some aspects of the present disclosure are directed to determining what data are relevant to be replayed. According to one exemplary embodiment, non-deterministic data is recorded for replay. It should be noted that there are many sources of non-deterministic behavior. In one exemplary embodiment, a processor 886,
According to various aspects, registers are classified by type of non-determinism and compressed in a type-specific manner. For example, one type of NDR is a peripheral register. Peripheral registers are registers present on the processor, but whose contents are controlled from sources external to the processor. For example, the value read from a register containing the value of an on-chip analog-to-digital (ADC) converter is non-deterministic. The number of bits that are needed to be stored can be determined by observing certain relationships; for example, a 10-bit ADC has 10 bits of non-determinism, despite the register being 16 bits in size.
Various exemplary compression schemes herein are designed to be lightweight in their use of compute resources. In various aspects, the compression is done in an opportunistic manner, e.g., whenever there is idle time on the processor. This can reduce the probability of violating an application's timing requirements. By using different compression schemes in an integrated manner in one system, an effective solution is presented for record and replay in a WSN.
TARDIS, in various aspects herein, can be used in situ to record deployed sensor nodes. An exemplary overall operational flow 100 is shown in
Non-application-specific code, e.g., data compression code and other TARDIS recording code 102, are compiled by compiler 112 or compiler 110, e.g., vanilla GCC, into object files 114. A linker 118, e.g., GCC or ld, combines object files 114, 116 to provide binary firmware 120 which will execute on the sensor node, and which includes TARDIS instrumentation for recording. An instrumentation map 122 is provided using instrumented object files 116, e.g., by extracting read IDs 258 from the parameter lists of calls to TARDIS routines, or other ways discussed herein.
In various examples, binary firmware 120 includes program instructions to detect when non-time-critical tasks are running and store data in Flash at such times. In an example, the program instructions schedule Flash data storage when an OS event queue or runnable-task queue is empty. In some examples, Flash data storage tasks can take priority over other tasks; in other examples, Flash data storage tasks have the lowest priority (other than the idle task). In some examples, the program instructions cause data to be stored in Flash when the processor would otherwise be going to sleep. Before the processor sleeps, the trace data are compressed and stored in Flash, in these examples. In some examples, Flash storage is handled by an OS task. This permits Flash storage to be interrupted by higher-priority tasks that carry out the normal operation of the system, and then resume once those higher-priority tasks complete.
Various aspects advantageously do not require support from a specific OS, so can be readily ported. TARDIS OS-specific code 108 in various tested examples is small and easy to port. Various aspects of TARDIS have been implemented on both TinyOS and Contiki operating systems.
Eight exemplary domains of non-determinism in a WSN are identified herein. These eight domains relate to specific approaches of compressing various types of non-deterministic events. The approaches discussed herein provide flexibility for a general-purpose software-only record and replay implementation for WSNs resulting in an 85-96% smaller trace size compared to the state-of-the-art control flow record and replay technique. The exemplary domains are in two major categories: reads from NDRs, and interrupts. For each category or domain, compression techniques are selected to record as few bits as possible for each such read or interrupt.
In a hypothetical example of a typical WSN application, a node takes a series of sensor readings every 20 seconds and forwards the associated data to a base station.
Examples of non-deterministic events that can be recorded to support deterministic replay include reads from peripheral registers and interrupts. Regarding reads, the processor can include peripheral registers that can be read by the processor, but whose values are set from external sources. For example, a processor can have a peripheral register designated to contain a data value of a most recent reading taken by an ADC. Regarding interrupts, the interrupt vector and the timing of the interrupt (e.g., at which instruction in the instruction stream was the interrupt signaled or did the interrupt service routine, ISR, begin execution) are both non-deterministic.
As stated above, the rate of non-deterministic data can be large. In one exemplary application, for one minute of real-time data acquisition, 5.4 MB of trace data may need to be recorded, which includes data recorded in every peripheral register and the timing of every interrupt. One source of non-deterministic data is a timer interrupt that takes place 64 times per second. This ISR for this interrupt starts by reading a register that indicates the purpose of the interrupt, and then it reads the current time from a timer register to check if any tasks are scheduled to be executed. In total, each call to the timer interrupt service handler requires logging several reads from NDRs. Moreover, even though the timing of the timer interrupt is known, different instructions can be interrupted each time the timer interrupt fires. Accordingly, data regarding the occurrence of the timer interrupt itself is non-deterministic. Another example is related to a radio. Even if a radio send rate is low, e.g., only every 20 seconds, the node can perform frequent tasks such as checking for radio messages being broadcast. The radio is normally off to save energy and is turned on several times a second to perform a clear channel assessment. Data read from the radio to perform that assessment are non-deterministic.
A trace of the size of 5.4 MB exceeds the RAM capacity of some embedded computers. Accordingly, such a trace can be stored in Flash memory. Flash is a significant consumer of energy, e.g., the Flash on an exemplary node draws a current of 15 mA during write. As a point of comparison, a sleeping node draws on the order of a few μA. Moreover, transmitting a large trace wirelessly to a base station can consume significant energy. Various aspects herein enable record and replay for WSNs by compressing the trace data without interfering with the real-time constraints of the system.
One exemplary type of NDR is a state register such as a peripheral register including a plurality of bitfields in a single processor word. Accordingly, register masking is a common programming pattern. Take for example the case of the interrupt flag register, where each bit represents a different condition. It is common to test one specific condition, so a mask is bitwise ANDed with the register. In the following exemplary line of C code, a mask (TXFLG) is applied to test if the transmit flag is set in the interrupt flag register (IFG):
- not_done_transmitting=IFG & TXFLG;
During replay of this line of code, an emulator will need to consult the recorded trace, because IFG is a non-deterministic peripheral register. However, it may be observed that in the case where a mask is applied, it is sufficient for deterministic replay to only know the value of the unmasked bits and not the entire value of the register. This can lead to a significant saving because a 16-bit register read can be potentially stored in a single bit (e.g., if TXFLG has only a single '1' bit). Various aspects check for the masked register pattern at compile time and instrument recording of peripheral register reads, accordingly, e.g., as discussed below with reference to
State registers can also be used in polling loops. An example of a polling loop is where the processor transmits a byte to the serial peripheral interface (SPI) bus, then it stays in a loop until the transmit complete flag is set, before transmitting the next byte. In the following exemplary line of C code, IFG is the interrupt flag register and TXFLG=1 is a mask for the least significant bit that is cleared when the byte has finished transmission:
- while (IFG & TXFLG) /* do nothing */;
This loop will read from the register IFG multiple times before the byte has finished being transmitted. A correct execution exits the polling loop. Infinite loops (e.g., due to hardware failures) can be terminated, e.g., by a watchdog timer. Moreover, the exemplary loop itself, like similar polling loops, does not modify global or local memory. Therefore, in various aspects, replay skips beyond the loop without losing the property of deterministic replay. There is however one consequence of skipping the loop, and that is losing the cycle accuracy of the replay. In some examples, the time to transmit a byte is predictable, e.g., because the SPI bus peripheral module typically uses a multiple of the same clock signal as the processor, and thus can be accounted for by the replay emulator. In some examples, a loop count (discussed below) is not incremented during polling loops that do not read or modify any data that is live after the polling loop exits.
A peripheral module register may exhibit a strong temporal locality. For example, a flag bit that indicates whether an overflow has occurred in a timer may usually be set to zero, because the overflow case is less common. Another example is with interrupt vector registers that indicate the purpose for an interrupt being signaled. A timer register may be signaled due to the timer reaching one of six capture/compare values. In a typical application, one of the capture/compare registers may be more frequently used than the others, resulting in the interrupt vector register often repeating the same value. For many application programs, most reads to registers reporting the status of a particular peripheral module have the same value on consecutive reads. This can be taken advantage of by having the replayer predict that the next read from a register is the same as the last read from that register, so only reads resulting in wrong predictions need to be logged. Accordingly, 89% to 93% of peripheral register reads do not need to be logged when applying this simple form of register prediction.
Timer registers are counters that are incremented on clock edges. When a timer register either overflows or reaches the value of a capture/compare register, a timer interrupt is fired. The timer register is typically read once following the timer interrupt. It may be read more times before the processor goes to sleep. In some examples, the first read of a timer following a timer interrupt is likely to result in a value which is close to the value of the capture/compare register that caused the interrupt, or zero if the interrupt was caused by an overflow. Successive reads to the timer register are likely to result in values that are small increments from one to the next. This is because, in these examples, the processor does not spend much time in active mode. All of the reads to the timer register following an interrupt happen within a small period of time. Thus, the difference between successive timer reads can be logged rather than the value of the timer register itself. For the first timer read following a timer interrupt the difference between the timer register value and the capture/compare register value (or zero for overflow) can be logged.
Two common WSN features, sensors and radios, account for another source of non-deterministic reads. Unlike the registers discussed above, these registers are not quite as simple to predict. However, in practice, they are quite compressible due to repeated sequences. For example, radio messages contain header information that is often similar from one message to the next. Routes do not change often, so consecutive messages are likely to be addressed to the same next hop neighbor. Sensor readings often have repeating values. In a tested example, the sensor and radio data registers can be compressed by 82% for one exemplary application.
Some exemplary application programs, such as programs for WSNs, are designed to last for a long time, e.g., months to years of unassisted execution. To achieve this, sensor applications are designed to have a very low duty cycle, with the processor on a sensor node spending most of its wall-clock time in a low-power sleep mode. The processor in these examples can be woken from sleep by an interrupt. A typical application wakes the processor dozens of times per second but for only very brief bursts (<1 ms) of activity. Small tasks are performed each time the node is woken up, such as checking if radio messages are being transmitted, taking sensor readings, or updating software based clocks that are based on the underlying hardware clocks. Because the processor is active for such a short amount of time the probability of an interrupt occurring when the processor is active is small. Therefore, the vast majority of interrupts in these examples (e.g., 95%-99%) occur when the node is in sleep mode. In some examples, there is only a single location in the code where the node can enter sleep. Accordingly, in various aspects, when recording interrupts that wake the node from sleep state, the timing (e.g., where within the instruction execution stream the interrupt occurred) or address for interrupts that happen during sleep are not recorded. Many interrupts are for timer ISRs that update the clock and then quickly go back to sleep. In some examples, only the interrupt vector is recorded, and the whole sleep period is considered to be atomic. In an example of the MSP430 processor, the interrupt vector takes 4 bits, the interrupted address takes 16 bits, and the loop count (discussed below) takes 16 bits. Saving only the vector can reduce the storage requirement for tracing an interrupt from 36 bits to 4 bits.
In the architecture of one exemplary sensor node, there are 16 interrupt service handlers. These handlers are for direct memory access (DMA), input/output (I/O), watchdog, timers, universal asynchronous receiver transmitters (USARTs), comparators, ADCs, and digital to analog converters (DACs). It is common in a typical application that most interrupts are to just a few of the interrupt service handlers. For example, a main timer interrupt handler in a typical application is called often (e.g., 64 times a second), while some other interrupt handlers may be called rarely or not at all. For example, not all applications use the DAC, the ADC, both timers, DMA, the watchdog timer, and both USART buses and therefore will not see interrupts from such peripherals. Another consequence of this observation is that a simple prediction type compression can be employed, in which it is predicted that the next interrupt service handler to be invoked will be the same as the last one. In a tested example, this prediction technique is correct about 85% of the time, so only about 15% of the interrupts will need to be logged.
In various application programs, all reads from peripheral registers are statically addressed. A static access means that the register is addressed directly and not by a pointer that can vary at runtime. In such programs, reads from peripheral registers can be readily identified and instrumented at compile time. Each peripheral register has a permanently assigned function defined in the architecture. Non-static reads can be traced by, e.g., manually instrumenting the target system code.
Various aspects are designed for single processor record and replay. Various aspects provide record and replay of multi-processor architectures, including recording the order of non-deterministic operations between processors or in multi-threaded code. In various examples, the thread scheduler is a part of the system being recorded and, therefore, is deterministic.
As noted above, sources of non-deterministic data to be recorded include reads from peripheral registers and interrupts. The method of encoding or compression applied to peripheral registers depends on their functionality. For example, registers with similar functions have common behaviors that can be exploited to improve compression. Classes of register functionality include: State, Data, and Timer. State registers include interrupt vectors, interrupt flags, overflow flags, and ready flags. Data registers contain general purpose I/O and bus data such as from a radio or sensor. Timer registers are counters that are incremented on the edge of a clock source. The clock may be asynchronous to the processor's clock making its value non-deterministic. Registers can be assigned to the three classes based on the architecture, e.g., based on processor documentation and embedded-system configuration.
State registers can be encoded using run length encoding (RLE). In at least one example, the recorder software maintains a last-read value and count since last change for each State register. In various examples, register masking and polling loop optimizations are applied to State registers as explained herein.
Data registers can be compressed using a generic compression algorithm, e.g., LZRW, which is a variant of the LZ77 family of compression algorithms, or other LZW compression algorithm such as S-LZW. The advantage of LZRW is that it has a very small memory footprint, which is useful in systems that have only kilobytes of memory. LZRW can be configured to use a sliding window size of 128 bytes along with a table of size of 64 bytes for a total implementation size of 192 bytes in RAM. In various aspects, a compression technique is chosen that will be effective for the data of interest. In various aspects, different compressors are used for specific data registers based on domain knowledge of what the registers will typically hold.
In various aspects, for both data and state registers, only the relevant bits are stored. The relevant bits can be determined by pattern-matching in source code (e.g., to detect masking operations) or by liveness analysis (e.g., to locate dead bits, bits that do not affect execution after an NDR read).
Timer registers are counters that are incremented on clock edges. As discussed herein, the time between timer reads is often predictable. The difference (delta) between the predicted value and the actual value can be encoded using, e.g., a Golomb prefix code. A Golomb prefix code shortens the encoded length of small values, which is beneficial because the delta is often zero, or very small. Moreover, in some examples, the delta is constant, even if its magnitude is large. Near-constant values have low entropy and are thus highly compressible.
A second source of non-deterministic data that can be recorded is interrupts. To deterministically reproduce an interrupt during replay, three pieces of information must be known: the interrupt vector, the interrupt's return address, and the loop count where the interrupt happened. The interrupt's return address tells at which instruction the interrupt occurred. However, because instructions repeat, a count of the number of loop iterations for all loops is also recorded. As described above, interrupts that wake the node from sleep do not need to have their return address or loop count recorded in some examples. This is because, in these examples, there is only one location in the system code that is responsible for putting the node to sleep (e.g., the system idle task). In some aspects, the return address is compressed expecting that a few addresses in the code tend to get interrupts far more often than others. These aspects use, e.g., a 16-entry return address cache. When there is a cache hit, the 4-bit index to the cache is recorded. Only when there is no cache hit and the interrupt did not happen during sleep does the full (e.g., 16-bit return) address need to be recorded. Other sizes of cache can be used. Cache eviction policies known in the microprocessor art can be used.
In various examples, a compiler component of TARDIS can be implemented as a plugin to a compiler such as the GNU Compiler Collection (GCC). The plugin can perform a pass over the target program, instrumenting it with loop counters and code to record peripheral register reads and interrupts. A loop counter is a single counter incremented by every loop in the program. The pass can occur after most of the compiler's middle-end optimizations, but before the target program is converted to the architecture dependent Register Transfer Logic (RTL) representation. This advantageously permits inserting loop counters after completion of loop optimizations, because some optimizations change the number or structure of loops in the final binary. This also permits using architecture-independent tracing code. The representation on which an exemplary plugin operates is called Gimple, which is a simple architecture independent intermediate representation language. Other compilers or representation languages can be used.
An exemplary compilation process is shown in
In various aspects, the trace 152 includes three streams: one stream of state and timer data, one stream of LZRW data, and one stream of interrupt data. The streams can be stored separately in trace 152. During replay, the replayer emulates execution of source, e.g., as described below with reference to
A single binary firmware 120 containing the application 104, OS 106, and TARDIS code 108 is programmed into a node. The runtime code for TARDIS is mostly OS agnostic. This code consists of encoding, buffering, and Flash logging. There is a small amount of code specific to the OS being instrumented, it includes calling the TARDIS initialization and update functions. The update function performs the check for buffers that are ready to be compressed or written to Flash. The scheduling of calling the update function is OS specific. Also, the part of the code that writes to Flash depends on the specific Flash and the interface it exposes to the software stack.
An emulator 180 is instrumented to perform the replay. The emulator 180 starts from a memory checkpoint or known starting state (e.g., boot-up). Whenever a read from a peripheral module register is encountered, an instrumentation map 122 generated at compile time (
The effort of porting TARDIS to various architectures would involve creating a new register definition file. This file describes which registers are non-deterministic, and maps registers to their type: State, Data, and Timer. Porting TARDIS to different OSes involves modifying the OS-specific code 108 shown in
Domain specific compression techniques used by TARDIS can significantly reduce trace size—2.3× to 88× less Flash usage than baseline record and replay—and operate with tolerable overheads for energy (1-57%), a noteworthy metric for WSNs, as well as CPU, RAM and program memory usage. Furthermore, when compared to prior control flow record and replay technique, it has been determined that TARDIS only uses 4% to 15% of the trace size of one exemplary prior art tracing application while being able to replay an execution more effectively.
Experiments were conducted with 9 nodes arranged in a grid with a 1 m separation between two adjacent nodes and the base station at a corner of the grid. The experiments involving a single node represented an inactive network (i.e., no radio traffic). The experiments were run for three exemplary benchmarks. Two of the exemplary benchmarks were representative of applications in exemplary OSes. A third benchmark was also chosen to test more extreme WSN scenarios. In the first exemplary benchmark, each node sampled a light sensor at a rate of 1 Hz, and forwarded the measurements to a base station every 5 readings. Each node's radio was turned on all of the time. Each node's CPU was configured to sleep until woken up because either it had some task to do (e.g., read the light sensor) or it was interrupted by the radio. Low Power Listening (LPL), a Media Access Control (MAC) level protocol where the radio is turned on at a fixed interval to perform a Clear Channel Assessment (CCA), and immediately turned back off if there is no activity, was used in some tests. In an inactive network, LPL provides the most significant energy savings.
The second benchmark was an exemplary application, where every 20 seconds each node sent a message containing readings for 5 different sensor sources.
According to the third benchmark, each node sampled a sensor, e.g., an accelerometer, at a rate of 100 Hz for 1 second. At the end of the sampling period the node performed a Fast Fourier Transform (FFT) on the sampled data, sent a message over the radio including FFT output data, and then began the next sampling period. The sample rate of 100 Hz is representative of operations in, e.g., earthquake monitoring WSNs. The third benchmark was run in a single hop mode with each node sending directly to a base node.
The runtime overhead includes the amount of Flash used to store trace, and the additional energy and CPU time expended for tracing. The runtime overhead of a network of 9 nodes for all three of the benchmark applications was determined. To understand the effect of network as well as LPL, single node (inactive network) and LPL results for one benchmark application were determined. The size of the Flash in a tested node was 1 MB.
TARDIS incurs CPU overhead only to record non-deterministic events and the first benchmark in the network mode case represents a worst case scenario where there are large numbers of non-deterministic events. In the experiments performed, the increase in energy due to the CPU is negligible when compared to energy due to other sources such as the radio.
Various aspects herein record the execution control flow without the external input data. One exemplary prior art tracer application ("TinyTracer") uses a static program analysis to encode inter- and intra-procedural control flow paths of concurrent events in a WSN application. Each benchmark application was run for 30 seconds and the results were recorded to Flash. Furthermore, for comparison reasons, uncompressed data for both TARDIS and TinyTracer was also recorded.
As shown in
There may be a gap of time between when a bug occurs to when it is detected by a developer. TARDIS is configured to store a long trace in time to increase the probability of being able to replay the bug.
A likely debugging scenario would be for a developer to observe increased congestion in the network, and then use TARDIS to replay execution of a node.
An exemplary application containing a known bug was executed and traced using TARDIS. The bug was in the radio module and resulted in a receiving node sending acknowledgment packets at the highest signal strength even when a lower signal strength had been specified in a parameter setting. The consequence of signaling at the highest signal strength was that it increased contention and collisions in the network thereby potentially reducing throughput. In an experiment, TARDIS traced 10.9 minutes of trace into 500 KB of Flash. In this time the tested node sent 5048 acknowledgments. In the experiment, the developer set a breakpoint during replay and examined the transmit signal strength for the acknowledgements. During replay it was observed that the signal strength value was not being correctly set.
Various aspects permit tracking causality across nodes through message sends and receives. Various aspects are useful in multi-threaded, simultaneous multi-threaded, or multi-process environments, in which additional non-determinism is introduced by different processes running concurrently in different threads or on different processors on the same computing device. For example, the order of shared memory accesses can be logged.
According to one aspect of the present disclosure, identification of registers to which non-deterministic data is written and thus used for record and replay can be automated. The peripheral registers for a type of processor are typically classified into one of three types: STATE, DATA and TIMER. The classification can be used to determine which method of compression is best suited for each of the peripheral registers on that type of processor. A table of classifications of the registers on the target processor type can be uploaded at compile time, so that reads from peripheral registers can be instrumented with a preferred compression method.
According to various aspects, a method for tracing program execution on a processor, e.g., an embedded processor, of a class of processors in an embedded device includes automatically performing the following steps using a processor, e.g., on a personal computer running a compiler: identifying a plurality of non-deterministic locations in the program where associated non-deterministic data are read from associated NDRs; identifying a plurality of interrupt locations in the program where interrupts occur; instrumenting the program to record register values in the associated NDRs at each of the identified plurality of non-deterministic locations into an uncompressed dataset; instrumenting the program to record interrupt occurrence of each interrupt and parameters associated with the interrupt into the uncompressed dataset; and compressing the uncompressed dataset into a compressed dataset. Various embodiments include communicating the compressed dataset to a base station.
An exemplary method for replaying program execution on a processor of a class of processors in an embedded device comprises automatically performing the following steps using a processor, e.g., in a base station or personal computer: receiving a compressed dataset at a base station; and replaying the compressed dataset at the base station, e.g., as described herein. The identifying a plurality of non-deterministic locations can include isolating instructions associated with retrieval of register values in the associated NDRs. The isolated instructions can include one or more of read, load, add, xor, and move instructions. The instrumenting the program to record register values can include replacing an associated instruction in the program to include loading the register values in the associated NDRs into one or more temporary registers; recording the values of the one or more temporary registers into the uncompressed dataset; and inserting a substitute instruction for the replaced associated instruction using data from the one or more temporary registers.
The identifying a plurality of non-deterministic locations can include ignoring (i.e., not identifying for tracing) non-deterministic locations inside of polling loops, e.g., polling loops on NDRs. Data of the recorded register values in the associated NDRs can be compressed by ignoring masked bits.
Compressing of the uncompressed dataset can include: classifying the plurality of NDRs into three types: STATE, DATA, and TIMER, and compressing data from each type into a corresponding sub-dataset using an associated compression algorithm. The classifying the plurality of NDRs can include: executing a predefined application program on a representative processor of the class of processors; recording values from each of the plurality of NDRs of the representative processor; compressing the recorded data for each of the plurality of NDRs based on register types of STATE, DATA, and TIMER, resulting in three compressed sub-datasets; comparing the size of the three compressed sub-datasets; selecting the register type associated with the smallest size of compressed sub-dataset; and associating each of the plurality of the NDRs with the selected register type in a table, e.g., stored in a computer-readable medium. The STATE peripheral register type can be compressed using a Run Length Encoding (RLE) algorithm. The DATA peripheral registers can be compressed using a Lempel-Ziv-Welch (LZW) algorithm, e.g., a Lempel-Ziv Ross Williams (LZRW) algorithm. The TIMER peripheral registers can be compressed by delta encoding. Parameters associated with an interrupt can include interrupt vectors, which can be compressed using an RLE algorithm.
Various aspects herein advantageously provide type-specific processing of non-deterministic data, e.g., compression. There are described herein a processor and computer-readable-medium carrying program instructions to cause the processor to carry out the run-time type-specific compression of non-deterministic data. There are described herein methods for, and computer-readable media carrying program instructions for, instrumenting source code to carry out type-specific compression in the context of tracing. There are also described herein methods for, and computer-readable media carrying program instructions for, carrying out type-specific decompression in the context of tracing, permitting improved debugging of, e.g., embedded systems such as WSNs. Also described herein are systems including multiple nodes, each having one or more processors, that intercommunicate and that each trace events and compress data in a type-specific way. Various aspects compress NDR reads only, compress interrupts only, or compress both NDR reads and interrupts.
A technical effect of various aspects described herein is to improve the functioning of computers by providing debugging trace data not previously available due to power and Flash-size constraints. A technical effect of various aspects described herein is to improve the technology of wireless sensor networks, e.g., for earthquake monitoring or bridge inspection, by providing increased robustness of software running on such networks and therefore increased uptime and effectiveness of such networks to carry out the measurements for which such networks are designed and deployed. A further technical effect is to present a visual representation of internal state of an embedded device, e.g., a trace screen of a node, on an electronic display.
Data storage system 840 can include or be communicatively connected with one or more processor-accessible memories configured or otherwise adapted to store information. The memories can be, e.g., within a chassis or as parts of a distributed system. The phrase "processor-accessible memory" is intended to include any data storage device to or from which processor 886 can transfer data (e.g., using appropriate components of data storage system 840 or peripheral system 820), whether volatile or nonvolatile; removable or fixed; electronic, magnetic, optical, chemical, mechanical, or otherwise. Exemplary processor-accessible memories include but are not limited to: registers, floppy disks, hard disks, tapes, bar codes, Compact Discs, DVDs, read-only memories (ROM), erasable programmable read-only memories (EPROM, EEPROM, or Flash), and random-access memories (RAMs).
The phrase "communicatively connected" includes any type of connection, wired or wireless, for communicating data between devices or processors. These devices or processors can be located in physical proximity or not. For example, subsystems such as peripheral system 820, user interface system 830, and data storage system 840 are shown separately from the processor 886 but can be stored completely or partially within the processor 886.
Various aspects herein may be embodied as computer program products including computer readable program code ("program code") stored on a computer readable medium, e.g., a tangible non-transitory computer storage medium or a communication medium. A computer storage medium can include tangible storage units such as volatile memory, nonvolatile memory, or other persistent or auxiliary computer storage media, removable and non-removable computer storage media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. A computer storage medium can be manufactured as is conventional for such articles, e.g., by pressing a CD-ROM or electronically writing data into a Flash memory. In contrast to computer storage media, communication media may embody computer-readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave or other transmission mechanism. As defined herein, computer storage media do not include communication media. That is, computer storage media do not include communications media consisting solely of a modulated data signal, a carrier wave, or a propagated signal, per se.
In an example, data storage system 840 includes RAM 841, e.g., a static RAM or dynamic RAM, and computer storage medium 843, e.g., a hard drive, Flash memory, or other nonvolatile computer storage medium. Computer program instructions are read into RAM 841 from computer storage medium 843 or a code memory therein. The code memory can include a portion of RAM 841 or computer storage medium 843 holding the computer program instructions, e.g., as binary firmware 120. Stored in the code memory are one or more module(s) 845 configured for execution by processor 886, the one or more modules including instructions to perform functions described herein. Processor 886 executes one or more sequences of the computer program instructions loaded into RAM 841, as a result performing process steps described herein. In this way, processor 886 carries out a computer implemented process. For example, steps of methods described herein with respect to
The peripheral system 820 can include or be communicatively connected with one or more devices configured or otherwise adapted to provide digital content records to the processor 886 or to take action in response to processor 186. For example, the peripheral system 820 can include or be communicatively connected with digital still cameras, digital video cameras, radios or other wireless communication devices, environmental sensors, or other data-providing devices. The processor 886, upon receipt of digital content records from a device in the peripheral system 820, can store such digital content records in the data storage system 840.
In the illustrated example, peripheral system 820 includes or is communicatively connected with a sensor 823. Sensor 823 is configured to monitor a target 888, graphically represented as a sun. Target 888 can be, e.g., the Earth, space, the environment around sensor 823, a machine, a bridge or other structure, a volume through which electromagnetic radiation may pass, or any other space, object, or field that can be sensed by sensor 823. In an example, sensor 823 includes a seismic sensor configured to periodically measure vibration. In the illustrated example, peripheral system 820 receives commands from, and communicates sensor 823 data to, processor 886 via data bus 825. Peripheral system 820 interrupts processor 886 using signals provided by interrupt request (IRQ) line 826. In an example, when sensor 823 has new data available, peripheral system 820 transmits a signal (e.g., a high logic level) on IRQ line 826. Processor 886 responds to that signal by executing program instructions of a corresponding interrupt service routine (ISR). The ISR or other code executed by processor 886 in response to the interrupt can read the new data via data bus 825.
In various aspects, module(s) 845 include computer program instructions to read data from a first NDR of a first type. Module(s) 845 can also include instructions to read data from a second, different NDR of a second, different type. Each of the first type and the second type can be, e.g., a state-register type, a data-register type, a timer-register type, or any other type of NDR described herein. Module(s) 845 can also include instructions to compress the data from the first NDR using a first compression algorithm to provide first compressed data, and instructions to compress the data from the second NDR using a second, different compression algorithm to provide second compressed data. Module(s) 845 can also include instructions to store the first and second compressed data in the nonvolatile medium, e.g., computer storage medium 843. Examples of these operations are discussed herein, e.g., with reference to
In various examples in which data storage system 840 includes a volatile computer storage medium such as RAM 841, the one or more module(s) 845 can include instructions to store the first and second compressed data in the volatile medium, e.g., before storing the first and second compressed data in the nonvolatile medium. Module(s) 845 can also include instructions to, subsequently, await an idle condition of the processor 886. An idle condition can be detected, e.g. when a task switcher in an OS running on the processor 886 transitions to the system idle process or is about to put the processor 886 to sleep. Module(s) 845 can also include instructions to, subsequently, execute the instructions to store the first and second compressed data in the nonvolatile medium, said instructions including instructions to retrieve the first and second compressed data from the volatile medium. In this way, comparatively time- and power-consuming Flash writes can take place when the processor 886 is idle and time and power are relatively less scarce than at high-load times. Examples of this are discussed above with reference to RAM 144,
In various examples using IRQ line 826 or otherwise supporting interrupts of processor 886, module(s) 845 can also include instructions to detect occurrence of a processor interrupt. Examples of such instructions include instructions to put the processor to sleep until an interrupt wakes up the processor, and instructions to busy-wait on an interrupt-pending flag of the processor. Module(s) 845 can also include instructions to determine a vector and a return address of the processor interrupt. Module(s) 845 can also include instructions to compress the determined vector and return address using a third compression algorithm different from the first and second compression algorithms to provide third compressed data. Module(s) 845 can also include instructions to store the third compressed data in the nonvolatile medium, or to store the third compressed data in the volatile medium, await an idle condition of processor 886, and then store the third compressed data in the nonvolatile medium.
The user interface system 830 can convey information in either direction, or in both directions, between a user 838 and the processor 886 or other components of computing device 801 or computing device 802. The user interface system 830 can include a mouse, a keyboard, another computer (connected, e.g., via a network or a null-modem cable), or any device or combination of devices from which data is input to the processor 886. The user interface system 830 also can include a display device, a processor-accessible memory, or any device or combination of devices to which data is output by the processor 886. The user interface system 830 and the data storage system 840 can share a processor-accessible memory. In an example, computing device 801 is a wireless sensor node lacking a user interface system 830, and computing device 802 is a desktop computer configured to retrieve data from computing device 801 and present the retrieved data to user 838 via a user interface system 830 of computing device 802.
In various aspects, processor 886 includes or is connected to communication interface 815 that is coupled via network link 816 (shown in phantom) to network 850. For example, communication interface 815 can include an integrated services digital network (ISDN) terminal adapter or a modem to communicate data via a telephone line; a network interface to communicate data via a local-area network (LAN), e.g., an Ethernet LAN, or wide-area network (WAN); or a radio to communicate data via a wireless link, e.g., WIFI or GSM. Communication interface 815 sends and receives electrical, electromagnetic or optical signals that carry digital or analog data streams representing various types of information across network link 816 to network 850. Network link 816 can be connected to network 850 via a switch, gateway, hub, router, or other networking device.
In various aspects, computing device 801 can communicate, e.g., via network 850, with a computing device 802, which can include the same types of components as computing device 801 but is not required to be identical thereto. Computing devices 801, 802 are communicatively connected via the network 850. Each computing device 801, 802 can execute computer program instructions to, e.g., read sensors 823 or otherwise participate in a network of computing devices such as nodes in a wireless sensor network.
Processor 886 can send messages and receive data, including program code, through network 850, network link 816 and communication interface 815. For example, a server can store requested code for an application program (e.g., a JAVA applet) on a tangible non-volatile computer storage medium to which it is connected. The server can retrieve the code from the medium and transmit it through network 850 to communication interface 815. The received code can be executed by processor 886 as it is received, or stored in data storage system 840 for later execution. Program code may execute, e.g., entirely on processor 886, partly on processor 886 and partly on a remote computer connected to network 850, or entirely on the remote computer.
In an example, a system includes a plurality of embedded computing devices 801, 802. Each computing device 801, 802 further includes a communication interface 815 and the one or more module(s) 845 of each embedded device include instructions to transmit the respective compressed data via the respective communication interface 815. Examples of such systems include wireless sensor networks, personal area networks, mobile ad hoc networks (MANETs), mesh networks, and other examples given above.
An "architecture" of an embedded device defines at least some registers or storage locations of that device or devices of the same type. An architecture can also define at least some instructions that operate on those registers or storage locations. Exemplary architectures include the TI MSP430, ARM ARM7 and ARMS, INTEL x86, and AMD AMD64 ("x64").
In step 902, one(s) of the instructions are located that read an NDR. The locating is performed using register data of the architecture. This can be, e.g., as described above with reference to compiler 112 and
In step 904, a register type of the NDR is determined using the register data. In the example of
In step 906, instruction(s) are added to the computer program product following the located instruction(s). The added instruction(s) including instruction(s) for use within the architecture to compress the value read by the located instruction(s) using a compression algorithm corresponding to the determined register type. In the example of
In decision step 908, it is determined whether there are any more NDR reads in the computer program product, e.g., application code 104. If so, the next step is step 902. In this way, the locating step 902, the determining step 904, and the adding step 906 are repeated for each of a plurality of located one(s) of the instructions of the computer program product using compression algorithms corresponding to the respective determined register types.
In step 1002, instructions of the computer program product corresponding to loops are located. This can be, e.g., as discussed above with respect to the IFG polling loop.
In step 1004, instructions(s) are added to the computer program product within the located loop. The added instructions(s) include instructions to increment a loop counter on each iteration of the loop. In an example expressed (without limitation) in the C programming language:
can be rewritten as
where "++" is an increment operator in the C programming language.
In step 1006, at least some of the instructions of the computer program product corresponding to an interrupt handler are located. For example, the contents of an interrupt vector table in application code 104 can be inspected and routines indicated therein selected for processing.
In step 1008, instruction(s) are added to the computer program product within the located interrupt handler. The added instruction(s) can include instructions for use within the architecture to compress a vector of the interrupt, a return address of the interrupt, and a current value of the loop counter using an interrupt-data compression algorithm to provide compressed interrupt data. Exemplary compression techniques are described above.
In step 1010, instruction(s) are added to the computer program product outside the located interrupt handler. The added instruction(s) including instructions for use within the architecture to store the compressed interrupt data on a non-volatile computer-readable medium. For example, the added instruction(s) can periodically execute and can check a buffer for new interrupt data, then compress such data if present.
In decision step 1012, it is determined whether additional interrupt handler(s) are present in the computer program product. If so, steps 1006, 1008, and 1010 can be repeated for one or more of the additional interrupt handler(s).
In various examples, the added instruction(s) for a data register type include instructions to compress at least part of the value read by the located instruction using a dictionary-based compression technique. In at least one aspect, no bit's value is stored unless that bit's value is required to accurately replay the execution or otherwise influences the execution of application program 104. In various examples, the added instruction(s) for a state register type include instructions to compress at least part of the value read by the located instruction using a run-length-encoding compression technique. In various examples, the added instruction(s) for a timer register type include instructions to compress at least part of the value read by the located instruction using a delta-encoding compression technique.
In step 1102, at least some of the instructions corresponding to a polling loop on an NDR are located. Polling loops on an NDR include an NDR in their loop condition (e.g., IFG in the example below). Polling loops for the purpose of step 1102 in at least one example do not modify any variables that will affect the execution sequence. For example, a polling loop can modify any number of variables as long as those variables are not used after termination of the loop.
In step 1104, instruction(s) are added to the computer program product following the located polling loop, the added instruction(s) including instructions for use within the architecture to compress information regarding exit of the polling loop and to store the compressed information on a non-volatile computer-readable medium. For example,
can be rewritten as
with suitable parameters to the tardis_record_loop_exit ( ) function call. Given the conditions above in step 1102, instruction(s) to record NDR reads (e.g., tardis_rle_record) are not added within the polling loop. This can be because the eventual result of the polling loop is deterministic, even if the time the loop takes to complete is not deterministic. In the example above, the value of IFG & TXFLG will not change until the loop exits, so leaving NDR reads in the polling loop unrecorded reduces the amount of data to be compressed. Instructions can be added within the polling loop to increment a loop counter, e.g., as described above with reference to step 1004. In at least one example, step 906 is not performed for any NDR read within a polling loop located by step 1102. In at least one example, step 902 does not locate NDR-read instructions within polling loops located by step 1102.
In step 1106, it is determined whether any NDR polling loops remain to be processed. If so, the next step is step 1102. In this way, steps 1102, 1104 can be repeated for each of a plurality of NDR polling loops in the computer program product.
Methods described in
At block 1204, emulation-target instructions and compressed data of NDR values are received, e.g., by processor 886 or another processor. The emulation-target instructions include first instructions to read NDRs and second instructions, e.g., instructions that do not read NDRs or that do not read NDRs of interest. In an example, the emulated-target instructions are instructions of application code 104 or a compiled version thereof. In some aspects, block 1204 of the emulator computer program mechanism includes instructions for receiving the compressed data of NDR values via a communications link, e.g., from WSN node(s). This can permit near-real-time inspection and debugging of system performance.
At block 1206, an execution sequence of the emulation-target instructions is emulated. The execution sequence is determined at least partly by the emulated-target instructions and at least partly by the data of the NDR values. Block 1206 can include blocks 1208-1226.
At block 1208, a next instruction in the execution sequence is retrieved. This can be done by, e.g., fetching the instruction in emulated memory corresponding to an emulated program counter (PC) or instruction pointer (IP).
At decision block 1210, it is determined whether the retrieved next instruction is a first instruction that reads an NDR or a second instruction. For first instructions, the next block is block 1216. For second instructions, the next block is block 1212.
At block 1212, an emulated-machine state is updated based on the retrieved next instruction. This can include updating emulated registers or emulated memory, taking input, providing output, or otherwise performing actions the emulation target would perform as a result of executing the next instruction. Block 1212 can include changing the instruction pointer so that the execution sequence changes.
At decision block 1214, it is determined whether there are more instructions to be emulated. If so, the next block is block 1208. Using block 1208, decision block 1210, block 1212, and decision block 1214, the emulated-machine state can be updated for each second instruction in the execution sequence.
At block 1216, the next instruction retrieved by block 1208 is a first instruction. A type of the NDR read by the next instruction is determined. This can be done using register data of the architecture of the emulation target, e.g., as discussed above with reference to step 904. In some aspects, the respective type of each NDR is a state-register type, a data-register type, or a timer-register type.
At block 1218, a portion of the compressed data is decompressed using a decompression algorithm corresponding to the determined register type. In the example above using IFG, the appropriate portion of the compressed data corresponding to the traced value of IFG can be decompressed. Other examples of decompression useful in block 1218 are discussed above.
At block 1220, the emulated-machine state is updated based on the decompressed portion or based on the decompressed portion and the next instruction, as necessary depending on the next instruction. Any of the state changes discussed above with reference to block 1212 can be used.
Block 1220 is followed by decision block 1214. Using block 1208, decision block 1210, block 1216, block 1218, block 1220, and decision block 1214, the emulated-machine state can be updated for each first instruction in the execution sequence. Using blocks 1212 and 1220 and other blocks noted above in conjunction, the full execution sequence of the emulation-target instructions can be emulated.
In various aspects, the emulator computer program mechanism (e.g., emulation module 1202) further comprises instructions to process interrupt data. These instructions can be used in conjunction with or instead of the above-described blocks 1208-1214 or any subset thereof.
At block 1222, compressed data of interrupts are decompressed, in part or wholly, using an interrupt-data decompression algorithm to provide interrupt data. The interrupt-data decompression algorithm can be different from data decompression algorithm(s) used in block 1218.
At decision block 1224, it is determined whether the execution sequence has reached a point at which an interrupt occurred. This can be done by, e.g., comparing a loop counter in the emulated-machine state or in the emulation module 1202 to a loop counter in the decompressed interrupt data. If not, emulation can continue with block 1208 or block 1222. If so, emulation can continue with block 1226.
At block 1226, the emulated-machine state is updated according to the interrupt data. Using block 1222, decision block 1224, and block 1226, the emulated-machine state can be updated at point(s) in the execution sequence indicated by the interrupt data. In this way, the emulator control program mechanism can effectively emulate non-deterministic interrupts, e.g., corresponding to receipt of messages from other nodes in a WSN. Block 1226 can be followed by block 1208 or block 1222.
At runtime, the record code in binary firmware 1320 logs events, e.g., values read from NDRs such as peripheral registers, polling loops, or interrupts. At replay time, the emulator uses the instrumentation map 1322 to decide which instructions access peripheral registers and thus need to be fed from the log, and to determine how to decode the items in that log.
In various examples, transformer 1302 can include computer program instructions or other structures to instrument interrupt handlers to record the interrupt handler's vector along with the return address and loop count at the point when an interrupt is executed. Transformer 1302 can also or alternatively instrument the application code 104 to record the timing of interrupts using a hardware based performance counter to count the number of branches. Transformer 1302 can instrument one or more (up to all) loop bodies in the code to include an increment instruction on a global loop counter.
This application is inclusive of combinations of the aspects described herein. References to "a particular aspect" (or "embodiment" or "version") and the like refer to features that are present in at least one aspect. Separate references to "an aspect" (or "embodiment") or "particular aspects" or the like do not necessarily refer to the same aspect or aspects; however, such aspects are not mutually exclusive, unless so indicated or as are readily apparent to one of skill in the art. The use of singular or plural in referring to "method" or "methods" and the like is not limiting. The word "or" is used in this disclosure in a non-exclusive sense, unless otherwise explicitly noted.
The invention has been described in detail with particular reference to certain preferred aspects thereof, but it will be understood that variations, combinations, and modifications can be effected by a person of ordinary skill in the art within the spirit and scope of the invention.
Claims (19)
Priority Applications (3)
|Application Number
|Priority Date
|Filing Date
|US201361893923P true
|PCT/US2014/058999 WO2015061022A1 (en)
|Debugging non-deterministic embedded systems
|US15/031,230 US10007592B2 (en)
|Debugging non-deterministic embedded systems
Applications Claiming Priority (1)
|Application Number
|Priority Date
|Filing Date
|US15/031,230 US10007592B2 (en)
|Debugging non-deterministic embedded systems
Publications (2)
|Publication Number
|Publication Date
|US20160314055A1 US20160314055A1 (en)
|US10007592B2 true US10007592B2 (en)
Family Applications (1)
|Application Number
|Priority Date
|Filing Date
|US15/031,230 Active 2034-10-19 US10007592B2 (en)
|Debugging non-deterministic embedded systems
Country Status (2)
|US10007592B2 (en)
|WO2015061022A1 (en)
Cited By (1)
|Publication number
|Priority date
|Publication date
|US20180260264A1 (en) *
|International Business Machines Corporation
|System and method of collecting serviceability data in containers based cloud infrastructure
Families Citing this family (9)
|Publication number
|Priority date
|Publication date
|US9628107B2 (en)
|International Business Machines Corporation
|Compression of floating-point data by identifying a previous loss of precision
|US9959299B2 (en)
|International Business Machines Corporation
|Compression-aware partial sort of streaming columnar data
|US9823996B2 (en)
|Landis+Gyr Innovations, Inc.
|Debugging code for controlling intelligent devices using log data from executed object code
|CN106354623B (en) *
|A kind of application program adjustment method and device based on linux
|US9798649B1 (en)
|Landis+Gyr Innovations, Inc.
|Debugging code controlling resource-constrained intelligent devices contemporaneously with executing object code
|US10579499B2 (en)
|International Business Machines Corporation
|Task latency debugging in symmetric multiprocessing computer systems
|US10628542B2 (en) *
|Intel Corporation
|Core-only system management interrupt
|US10515092B2 (en)
|Google Llc
|Structured record compression and retrieval
|WO2020041730A1 (en) *
|The Trustees Of Dartmouth College
|Microcontroller for recording and storing physiological data
Citations (13)
|Publication number
|Priority date
|Publication date
|US7043668B1 (en)
|Mips Technologies, Inc.
|Optimized external trace formats
|US7178133B1 (en)
|Mips Technologies, Inc.
|Trace control based on a characteristic of a processor's operating state
|US7181728B1 (en)
|Mips Technologies, Inc.
|User controlled trace records
|US7185234B1 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US20070180333A1 (en)
|Mips Technologies, Inc.
|External trace synchronization via periodic sampling
|US20080086730A1 (en) *
|Marc Vertes
|Predictive Method for Managing Logging or Replaying Non-Deterministic Operations within the Execution of an Application Process
|US20090282294A1 (en) *
|David Alan Edwards
|Debugging System and Method
|US20090313460A1 (en)
|National Tsing Hua University
|Trace compression method for debug and trace interface of microprocessor
|WO2010002489A1 (en)
|Vmware, Inc.
|Efficient recording and replaying of non-deterministic instructions in a virtual machine and cpu therefor
|US7770156B2 (en)
|Mips Technologies, Inc.
|Dynamic selection of a compression algorithm for trace data
|US20100251031A1 (en)
|Jason Nieh
|Systems and methods for recording and replaying application execution
|US20110047360A1 (en) *
|Linear Algebra Technologies Limited
|US20120011491A1 (en)
|Adi Eldar
|Efficient recording and replaying of the execution path of a computer program
- 2014-10-03 US US15/031,230 patent/US10007592B2/en active Active
- 2014-10-03 WO PCT/US2014/058999 patent/WO2015061022A1/en active Application Filing
Patent Citations (18)
|Publication number
|Priority date
|Publication date
|US7644319B2 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US7178133B1 (en)
|Mips Technologies, Inc.
|Trace control based on a characteristic of a processor's operating state
|US7181728B1 (en)
|Mips Technologies, Inc.
|User controlled trace records
|US7185234B1 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US20070180333A1 (en)
|Mips Technologies, Inc.
|External trace synchronization via periodic sampling
|US20070180327A1 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US7770156B2 (en)
|Mips Technologies, Inc.
|Dynamic selection of a compression algorithm for trace data
|US7412630B2 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US20090037704A1 (en)
|Mips Technologies, Inc.
|Trace control from hardware and software
|US8185879B2 (en)
|Mips Technologies, Inc.
|External trace synchronization via periodic sampling
|US7043668B1 (en)
|Mips Technologies, Inc.
|Optimized external trace formats
|US20080086730A1 (en) *
|Marc Vertes
|Predictive Method for Managing Logging or Replaying Non-Deterministic Operations within the Execution of an Application Process
|US20110047360A1 (en) *
|Linear Algebra Technologies Limited
|US20090282294A1 (en) *
|David Alan Edwards
|Debugging System and Method
|US20090313460A1 (en)
|National Tsing Hua University
|Trace compression method for debug and trace interface of microprocessor
|WO2010002489A1 (en)
|Vmware, Inc.
|Efficient recording and replaying of non-deterministic instructions in a virtual machine and cpu therefor
|US20100251031A1 (en)
|Jason Nieh
|Systems and methods for recording and replaying application execution
|US20120011491A1 (en)
|Adi Eldar
|Efficient recording and replaying of the execution path of a computer program
Non-Patent Citations (21)
|Choudhuri, S. et al., "FlashBox: A System for Logging Non-Deterministic Events in Deployed Embedded Systems", SAC, Mar. 8-12, 2009, 7 pages.
|Dunlap, G.W., et al., "Execution Replay for Multiprocessor Virtual Machines", VEE, Mar. 5-7, 2008, 10 pages.
|Erikssen, J., et al., "Demo Abstract: Accurate Power Profiling of Sensomets with the COOJA/MSPsim Simulator", IEEE, Nov. 2009, 3 pages.
|Geels, D., et al., "Friday: Global Comprehension for Distributed Replay", NSDI 2007, 14 pages.
|Geels, D., et al., "Replay Debugging for Distributed Applications", USENIX Annual Technical Conference, 2006, 12 pages.
|Georges, A., et al., JaRec: A Portable Record/Replay Environment for Multi-Threaded Java Applications, Software-Practice and Experience, 2004, vol. 34, pp. 523-547.
|Guo, Z., et al., "R2: An Application-Level Kernel for Record and Replay", 8th USENIX Symposium on Operating Systems Design and Implementation, 16 pages.
|Huang, J., et al., "LEAP: The Lightweigh Deterministic Multi-Processor Replay of Concurrent Java Programs", FSE-18, Nov. 7-11, 2010, 10 pages.
|Leblanc, T.J., et al., Debugging Parallel Programs with Instrant Replay, IEEE Transactions on Computers, vol. C-36, No. 4, Apr. 1987, pp. 471-482.
|PCT Search Report and Written Opinion dated Jan. 9, 2015 for PCT application No. PCT/US2014/058999, 14 pages.
|Ronsse, M., et al., "RecPlay: A Fully Integrated Practical Record/Replay System", ACM Transactions on Computer Systems, vol. 17, No. 2, May 1999, pp. 133-152.
|Sundaram, V., et al., "Efficient Diagnostic Tracing for Wireless Sensor Networks", SenSys, Nov. 3-5, 2010, 14 pages.
|Sundaram, V., et al., "Prius: Generic Hybrid Trace Compression for Wireless Sensor Networks", SenSys, Nov. 6-9, 2012, 14 pages.
|Tancreti, M., et al., "Aveksha: A Hardware-Software Approach for Non-Intrusive Tracing and Profiling of Wireless Embedded Systems", SenSys, Nov. 1-4, 2011, 14 pages.
|Thane, H., et al., "Using Deterministic Replay for Debugging of Distributed Real-Time Systems", Proceedings-Euromicro conference on Real-Time Systems, Jan. 2000, 8 pages.
|Thane, H., et al., "Using Deterministic Replay for Debugging of Distributed Real-Time Systems", Proceedings—Euromicro conference on Real-Time Systems, Jan. 2000, 8 pages.
|Wang, M., et al., "Dependence-Based Multi-Level Tracing and Replay for Wireless Sensor Networks Debugging", LCTES, Apr. 11-14, 2011, 10 pages.
|Williams, "An Extremely Fast ZIV-Lempel Data Compression Algorithm", in the Proceedings of the 1991 IEEE Data Compression Conference, Apr. 1991, pp. 362-371.
|Wu, M., et al., Language-Based Replay Via Data Flow Cut, FSE-18, Nov. 7-11, 2010, 10 pages.
|Yang, J., et al., "Clairvoyant: A Comprehensive Source-Level Debugger for Wireless Sensor Networks", SenSys '07, Nov. 6-9, 2007, 16 pages.
|Ziv, J., et al., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977, pp. 337-343.
Cited By (2)
|Publication number
|Priority date
|Publication date
|US20180260264A1 (en) *
|International Business Machines Corporation
|System and method of collecting serviceability data in containers based cloud infrastructure
|US10606682B2 (en) *
|International Business Machines Corporation
|System and method of collecting serviceability data in containers based cloud infrastructure
Also Published As
|Publication number
|Publication date
|WO2015061022A1 (en)
|WO2015061022A8 (en)
|US20160314055A1 (en)
Similar Documents
|Publication Date
|US9389992B2 (en)
|Multiple tracer configurations applied on a function-by-function level
|Li et al.
|An investigation into energy-saving programming practices for android smartphone app development
|US9298589B2 (en)
|User interaction analysis of tracer data for configuring an application tracer
|US20190146785A1 (en)
|Diagnosing Production Applications
|US20170132111A1 (en)
|Monitoring mobile application performance
|US9021445B2 (en)
|Tracer list for automatically controlling tracer behavior
|US8978016B2 (en)
|Error list and bug report analysis for configuring an application tracer
|US9575874B2 (en)
|Error list and bug report analysis for configuring an application tracer
|Hoefler et al.
|LogGOPSim: simulating large-scale applications in the LogGOPS model
|Falaki et al.
|SystemSens: a tool for monitoring usage in smartphone research deployments
|US10031834B2 (en)
|Cache-based tracing for time travel debugging and analysis
|Dunkels et al.
|Run-time dynamic linking for reprogramming wireless sensor networks
|Kwon et al.
|Mantis: Automatic performance prediction for smartphone applications
|EP3213217B1 (en)
|Historical control flow visualization in production diagnostics
|US10031833B2 (en)
|Cache-based tracing for time travel debugging and analysis
|JP5705084B2 (en)
|2-pass automatic application measurement
|US20150347277A1 (en)
|Real Time Analysis of Tracer Summaries to Change Tracer Behavior
|Li et al.
|T-check: bug finding for sensor networks
|Khan et al.
|Dustminer: troubleshooting interactive complexity bugs in sensor networks
|US10042737B2 (en)
|Program tracing for time travel debugging and analysis
|JP2019537782A (en)
|System, method and device for vertically integrated instrumentation and trace reconstruction
|US8453123B2 (en)
|Time-based trace facility
|Yang et al.
|Clairvoyant: a comprehensive source-level debugger for wireless sensor networks
|Carbin et al.
|Detecting and escaping infinite loops with jolt
|EP2976715B1 (en)
|Application testing and analysis
Legal Events
|Information on status: patent grant
Free format text: PATENTED CASE


text:
THIS is how your child sees all these 'normal days'
When it comes to parenting, we all strive to do our best, I think.
We want our children to have the happiest of childhoods, filled with snuggles and cupcake baking and fun days at the park. Fear of them ever being bored, or missing out on anything, we fill afternoons with crafts and playdates, organise, sign them up to activity after activity. Pinterest and Instagram, and Facebook too, all add to this perfection pressure parents now feel, especially us mums, I think, as we are the biggest consumers of this type of social media.
In ways it's only natural, I suppose, wanting to be a great parent, wanting our children to remember a childhood that only had good days. Where magic happened, where there was always freshly baked cookies, where rooms were tidy and where there was no "hurry-up-we-are-going-to-be-late" mornings, no tired mum who struggled to keep it all together.
Strive as we may for this, the reality is that we are also only human. There will be days when we don't have it all together. Where the toast is burned and the cornflakes end up on the floor. Where we get no fun activities in but instead have to spend the day scrubbing bathrooms or getting the shopping done. Where we have slept only three hours and consumed far too much coffee and can only barely manage to keep the kids alive and fed, no glitter glue projects or jumping through leaves at the park.
The thing is, how we view our days, how we measure our success at motherhood, this all looks very different when seen through your child's eyes. Because where we see just a normal, messy, didn't-quite-live-up-to-my-mum-goals day, our children see something else. Something far more real and important.
This video will put things in perspective, we think. Make you embrace all those 'normal' days, and not only that, but feel good about them too:

subset: commoncrawl


text:
Families First Coronavirus Response Act - information for employees HERE
"The three-part question was about dividing fractions and used a scenario based on ordering pizza. If a teacher had 31 students in his room and every kid got a fourth of a pizza, how many pizzas need to be ordered?" said Rogers. "In the first part, students had to model division of fractions by either creating a diagram or drawing. In the second part, students were asked to use the standard algorithm to solve the problem. And the third part was to see how they could take that knowledge and apply it to extend their reasoning to explain their solution and why it was a realistic answer."
McMahan and Rogers discovered that the third part of the question presented a great deal of trouble for a majority of their students. They had difficulty explaining why their answer was reasonable, primarily because many of their answers were not practical at all.
"Instead of thinking backwards and multiplying, they focused on dividing fractions and trying to remember how to do that," Rogers said. "They didn't use reasoning or apply any number sense and told us we needed to order 134 pizzas, which is not a reasonable answer."
Rogers and McMahan realized they were going to have to find a way to teach their students to talk through math problems, to think about the problem before they attempted to solve it and to use number sense to determine if the answer was reasonable.
"We needed to help them make sense of not only the problem, but in connecting the problem to the answer and determining whether or not it's going to work," McMahan said.
In the description of their presentation, the math teachers offered to provide "an interactive discussion that shows how giving students number talks can be a powerful tool that math teachers use to increase rigor, encourage critical thinking, promote number sense, and display multiple strategies to solving problems. The focus of this presentation is to give middle school math educators some examples on how to incorporate number talks into their lesson plans to help foster mathematical minds and build a math community."
It's done just that at HCMS.
Using small groups of mixed ability levels, Rogers and McMahan began leading "number talks" with their students, literally talking through the problem. They started with the pizza question.
"We asked, 'Why is it that this answer does or does not make sense? Why is it that this is a reasonable answer versus 134 pizzas for 31 kids?'" Rogers said.
Fast forward several months of school and lots of number talks later, and both teachers are seeing results in their classrooms.
"What's exciting is that at this point in the school year our students are leading those conversations," McMahan said, pointing out that building the small group dynamic has resulted in improvement for all students. "In the past, the higher achieving student would just work and solve and not even know how to explain how they got the answer. And you've have a lower level kid who was embarrassed to ask questions, and the mid-level student just hovered between the two. Now, it's more natural for all students in a group to engage with each other in that discussion. The lower level kids feel more secure in answering. Sometimes their approach is different, but it's valid. It's just a different way of thinking about the problem. It builds confidence in students who may not have had it by providing them with a voice to explore options that other kids at the table may not have considered, regardless of whether they are right or wrong."
Rogers pointed out that students are much more receptive to considering multiple strategies, instead of subscribing to the idea that there's only one way to solve a problem. It also initiates the thought process for students, pushing them to think about what they are going to do before they do it. When the answer better connects to the question, students have more "ah hah" moments. Both Rogers and McMahan have seen "drastic improvement" from their students in subsequent extended response questions.
"It helps students understand not just how to get the right answer, but to understand the math reasoning behind the answer and why the answer goes with that problem. You have to be able to apply it – you need to understand the process of it, how to problem-solve," Rogers said. "We live in a society now where we need problem-solvers, we need people who understand why things work the way they do."


text:
Hashem Ejaz
Finance Graduate
Working with LBG's executive board, paving the way for research into autism in the workplace and visiting Amsterdam with his team – all while gaining an industry recognised accounting qualification – Hashem Ejaz reflects on his LBG journey so far.
Right at the heart
"Finance is at the core of Lloyds Banking Group – we need to know exactly what is going on and what's happening in the industry. I interact with a lot of shareholders and higher management, whether that's to relay figures or discuss how we can take the bank forward."
A broad view
"The Graduate programme provides greater variety to develop well-rounded skill sets. I worked across three different cities in a number of great roles, such as working in our Investor Relations team, helping shape the LBG story to the external market. I also spent six months in a Halifax branch, which was something completely different – seeing people come in with a problem and leave with a smile. It was hard work, dealing with customers on the frontline, but I could actually see how we were helping them. It was amazing!"
Learning the trade
"During the scheme, I studied to become a qualified chartered accountant. With exams every few months, balancing study and work was a new challenge but I received great support throughout and it helped me understand the fundamentals of the finance aspect of my roles. There's also the added bonus of gaining a qualification that's recognised across the globe and multiple industries."
Leading national research
"I've been working for a charity called Ambitious About Autism. They wanted to help people with autism to enter the workplace, so we created a pack of information showing how people with autism have unique skills. We then distributed it to employers to show them how these skills could help their business. The project was a huge success."
Social butterfly
"I joined LBG in September and by the following February, a number of my team took a trip to Amsterdam – sightseeing activities, the works. It shows you how quickly you build up friendships here – the social scene is brilliant and it's great to have friends in every location you work in."
Read next
Meet Our People
Meet our people
Compare our programmes
Compare our programmes
Training and Development
Training and development
Rewards and Benefits
Rewards and benefits
Our application process