1
0

acidpaper.html 46 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369
  1. <html>
  2. <title>
  3. data
  4. </title>
  5. <body BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#330088" ALINK="#FF0044">
  6. <H1>Acid: A Debugger Built From A Language
  7. </H1>
  8. <DL><DD><I>Phil Winterbottom<br>
  9. philw@plan9.bell-labs.com<br>
  10. </I></DL>
  11. <DL><DD><H4>ABSTRACT</H4>
  12. <DL>
  13. <DT><DT>&#32;<DD>
  14. NOTE:<I> Originally appeared in
  15. Proc. of the Winter 1994 USENIX Conf.,
  16. pp. 211-222,
  17. San Francisco, CA
  18. </I><DT>&#32;<DD></dl>
  19. <br>
  20. Acid is an unusual source-level symbolic debugger for Plan 9. It is implemented
  21. as a language interpreter with specialized primitives that provide
  22. debugger support. Programs written in the language manipulate
  23. one or more target processes; variables in the language represent the
  24. symbols, state, and resources of those processes.
  25. This structure allows complex
  26. interaction between the debugger and the target program and
  27. provides a convenient method of parameterizing differences between
  28. machine architectures.
  29. Although some effort is required to learn
  30. the debugging language, the richness and flexibility of the
  31. debugging environment encourages new ways of reasoning about the way
  32. programs run and the conditions under which they fail.
  33. </DL>
  34. <H4>1 Introduction
  35. </H4>
  36. <P>
  37. The size and complexity
  38. of programs have increased in proportion to processor speed and memory but
  39. the interface between debugger and programmer has changed little.
  40. Graphical user interfaces have eased some of the tedious
  41. aspects of the interaction. A graphical interface is a convenient
  42. means for navigating through source and data structures but provides
  43. little benefit for process control.
  44. The introduction of a new concurrent language, Alef [Win93], emphasized the
  45. inadequacies of the existing Plan 9 [Pike90] debugger
  46. <I>db</I>,
  47. a distant relative of
  48. <I>adb</I>,
  49. and made it clear that a new debugger was required.
  50. </P>
  51. <P>
  52. Current debuggers like
  53. <I>dbx</I>,
  54. <I>sdb</I>,
  55. and
  56. <I>gdb</I>
  57. are limited to answering only the questions their authors
  58. envisage. As a result, they supply a plethora
  59. of specialized commands, each attempting to anticipate
  60. a specific question a user may ask.
  61. When a debugging situation arises that is beyond the scope
  62. of the command set, the tool is useless.
  63. Further,
  64. it is often tedious or impossible to reproduce an anomalous state
  65. of the program, especially when
  66. the state is embedded in the program's data structures.
  67. </P>
  68. <P>
  69. Acid applies some ideas found in CAD software used for
  70. hardware test and simulation.
  71. It is based on the notion that the state and resources of a program
  72. are best represented and manipulated by a language. The state and resources,
  73. such as memory, registers, variables, type information and source code
  74. are represented by variables in the language.
  75. Expressions provide a computation mechanism and control
  76. statements allow repetitive or selective interpretation based
  77. on the result of expression evaluation.
  78. The heart of the Acid debugger is an interpreter for a small typeless
  79. language whose operators mirror the operations
  80. of C and Alef, which in turn correspond well to the basic operations of
  81. the machine. The interpreter itself knows nothing of the underlying
  82. hardware; it deals with the program state and resources
  83. in the abstract.
  84. Fundamental routines to control
  85. processes, read files, and interface to the system are implemented
  86. as builtin functions available to the interpreter.
  87. The actual debugger functionality is coded
  88. in Acid; commands are implemented as Acid functions.
  89. </P>
  90. <P>
  91. This language-based approach has several advantages.
  92. Most importantly, programs written in Acid, including most of the
  93. debugger itself, are inherently portable.
  94. Furthermore, Acid avoids the limitations other debuggers impose when
  95. debugging parallel programs. Instead of embedding a fixed
  96. process model in the debugger, Acid allows the
  97. programmer to adapt the debugger to handle an
  98. arbitrary process partitioning or program structure.
  99. The ability to
  100. interact dynamically with an executing process provides clear advantages
  101. over debuggers constrained to probe a static image.
  102. Finally, the Acid language is a powerful vehicle for expressing
  103. assertions about logic, process state, and the contents of data structures.
  104. When combined with dynamic interaction it allows a
  105. limited form of automated program verification without requiring
  106. modification or recompilation of the source code.
  107. The language is also an
  108. excellent vehicle for preserving a test suite for later regression testing.
  109. </P>
  110. <P>
  111. The debugger may be customized by its users; standard
  112. functions may be modified or extended to suit a particular application
  113. or preference.
  114. For example, the kernel developers in our group require a
  115. command set supporting assembler-level debugging while the application
  116. programmers prefer source-level functionality.
  117. Although the default library is biased toward assembler-level debugging,
  118. it is easily modified to provide a convenient source-level interface.
  119. The debugger itself does not change; the user combines primitives
  120. and existing Acid functions in different ways to
  121. implement the desired interface.
  122. </P>
  123. <H4>2 Related Work
  124. </H4>
  125. <P>
  126. DUEL [Gol93], an extension to
  127. <I>gdb</I>
  128. [Stal91], proposes using a high level expression evaluator to solve
  129. some of these problems. The evaluator provides iterators to loop over data
  130. structures and conditionals to control evaluation of expressions.
  131. The author shows that complex state queries can be formulated
  132. by combining concise expressions but this only addresses part of the problem.
  133. A program is a dynamic entity; questions asked when the program is in
  134. a static state are meaningful only after the program has been `caught' in
  135. that state. The framework for manipulating the program is still as
  136. primitive as the underlying debugger. While DUEL provides a means to
  137. probe data structures it entirely neglects the most beneficial aspect
  138. of debugging languages: the ability to control processes. Acid is structured
  139. around a thread of control that passes between the interpreter and the
  140. target program.
  141. </P>
  142. <P>
  143. The NeD debugger [May92] is a set of extensions to TCL [Ous90] that provide
  144. debugging primitives. The resulting language, NeDtcl, is used to implement
  145. a portable interface between a conventional debugger, pdb [May90], and
  146. a server that executes NeDtcl programs operating on the target program.
  147. Execution of the NeDtcl programs implements the debugging primitives
  148. that pdb expects.
  149. NeD is targeted at multi-process debugging across a network,
  150. and proves the flexibility of a language as a means of
  151. communication between debugging tools. Whereas NeD provides an interface
  152. between a conventional debugger and the process it debugs, Acid is the
  153. debugger itself. While NeD has some of the ideas
  154. found in Acid it is targeted toward a different purpose. Acid seeks to
  155. integrate the manipulation of a program's resources into the debugger
  156. while NeD provides a flexible interconnect between components of
  157. the debugging environment. The choice of TCL is appropriate for its use
  158. in NeD but is not suitable for Acid. Acid relies on the coupling of the type
  159. system with expression evaluation, which are the root of its design,
  160. to provide the debugging primitives.
  161. </P>
  162. <P>
  163. Dalek [Ols90] is an event based language extension to gdb. State transitions
  164. in the target program cause events to be queued for processing by the
  165. debugging language.
  166. </P>
  167. <P>
  168. Acid has many of the advantages of same process or
  169. <I>local</I>
  170. <I>agent</I>
  171. debuggers, like Parasight [Aral], without the need for dynamic linking or
  172. shared memory.
  173. Acid improves on the ideas of these other systems by completely integrating
  174. all aspects of the debugging process into the language environment. Of
  175. particular importance is the relationship between Acid variables,
  176. program symbols, source code, registers and type information. This
  177. integration is made possible by the design of the Acid language.
  178. </P>
  179. <P>
  180. Interpreted languages such as Lisp and Smalltalk are able to provide
  181. richer debugging environments through more complete information than
  182. their compiled counterparts. Acid is a means to gather and represent
  183. similar information about compiled programs through cooperation
  184. with the compilation tools and library implementers.
  185. </P>
  186. <H4>3 Acid the Language
  187. </H4>
  188. <P>
  189. Acid is a small interpreted language targeted to its debugging task.
  190. It focuses on representing program state and addressing data rather than
  191. expressing complex computations. Program state is
  192. <I>addressable</I>
  193. from an Acid program.
  194. In addition to parsing and executing expressions and providing
  195. an architecture-independent interface to the target process,
  196. the interpreter supplies a mark-and-scan garbage collector
  197. to manage storage.
  198. </P>
  199. <P>
  200. Every Acid session begins with the loading of the Acid libraries.
  201. These libraries contain functions, written in Acid, that provide
  202. a standard debugging environment including breakpoint management,
  203. stepping by instruction or statement, stack tracing, and
  204. access to variables, memory, and registers.
  205. The library contains 600 lines of Acid code and provides
  206. functionality similar to
  207. <I>dbx</I>.
  208. Following the loading of the system library, Acid loads
  209. user-specified libraries; this load sequence allows the
  210. user to augment or override the standard commands
  211. to customize the debugging environment. When all libraries
  212. are loaded, Acid issues an interactive prompt and begins
  213. evaluating expressions entered by the user. The Acid `commands'
  214. are actually invocations of builtin primitives or previously defined
  215. Acid functions. Acid evaluates each expression as it is entered and
  216. prints the result.
  217. </P>
  218. <H4>4 Types and Variables
  219. </H4>
  220. <P>
  221. Acid variables are of four basic types:
  222. <I>integer</I>,
  223. <I>string</I>,
  224. <I>float</I>,
  225. and
  226. <I>list</I>.
  227. The type of a variable is inferred by the type of the right-hand side of
  228. an assignment expression.
  229. Many of the operators can be applied to more than
  230. one type; for these operators the action of the operator is determined
  231. by the type of its operands.
  232. For example,
  233. the
  234. <TT>+</TT>
  235. operator adds
  236. <I>integer</I>
  237. and
  238. <I>float</I>
  239. operands, and concatenates
  240. <I>string</I>
  241. and
  242. <I>list</I>
  243. operands.
  244. Lists are the only complex type in Acid; there are no arrays, structures
  245. or pointers. Operators provide
  246. <TT>head</TT>,
  247. <TT>tail</TT>,
  248. <TT>append</TT>
  249. and
  250. <TT>delete</TT>
  251. operations.
  252. Lists can also be indexed like arrays.
  253. </P>
  254. <P>
  255. Acid has two levels of scope: global and local.
  256. Function parameters and variables declared in a function body
  257. using the
  258. <TT>local</TT>
  259. keyword are created at entry to the function and
  260. exist for the lifetime of a function.
  261. Global variables are created by assignment and need not be declared.
  262. All variables and functions in the program
  263. being debugged are entered in the Acid symbol table as global
  264. variables during Acid initialization.
  265. Conflicting variable names are resolved by prefixing enough `$' characters
  266. to make them unique.
  267. Syntactically, Acid variables and target program
  268. symbols are referenced identically.
  269. However, the variables are managed differently in the Acid
  270. symbol table and the user must be aware of this distinction.
  271. The value of an Acid variable is stored in the symbol
  272. table; a reference returns the value.
  273. The symbol table entry for a variable or function in the target
  274. program contains the address of that symbol in the image
  275. of the program. Thus, the value of a program variable is
  276. accessed by indirect reference through the Acid
  277. variable that has the same name; the value of an Acid variable is the
  278. address of the corresponding program variable.
  279. </P>
  280. <H4>5 Control Flow
  281. </H4>
  282. <P>
  283. The
  284. <TT>while</TT>
  285. and
  286. <TT>loop</TT>
  287. statements implement looping.
  288. The former
  289. is similar to the same statement in C.
  290. The latter evaluates starting and ending expressions yielding
  291. integers and iterates while an incrementing loop index
  292. is within the bounds of those expressions.
  293. <DL><DT><DD><TT><PRE>
  294. acid: i = 0; loop 1,5 do print(i=i+1)
  295. 0x00000001
  296. 0x00000002
  297. 0x00000003
  298. 0x00000004
  299. 0x00000005
  300. acid:
  301. </PRE></TT></DL>
  302. The traditional
  303. <TT>if-then-else</TT>
  304. statement implements conditional execution.
  305. </P>
  306. <H4>6 Addressing
  307. </H4>
  308. <P>
  309. Two indirection operators allow Acid to access values in
  310. the program being debugged.
  311. The
  312. <TT>*</TT>
  313. operator fetches a value from the memory image of an
  314. executing process;
  315. the
  316. <TT>@</TT>
  317. operator fetches a value from the text file of the process.
  318. When either operator appears on the left side of an assignment, the value
  319. is written rather than read.
  320. </P>
  321. <P>
  322. The indirection operator must know the size of the object
  323. referenced by a variable.
  324. The Plan 9 compilers neglect to include this
  325. information in the program symbol table, so Acid cannot
  326. derive this information implicitly.
  327. Instead Acid variables have formats.
  328. The format is a code
  329. letter specifying the printing style and the effect of some of the
  330. operators on that variable.
  331. The indirection operators look at the format code to determine the
  332. number of bytes to read or write.
  333. The format codes are derived from the format letters used by
  334. <I>db</I>.
  335. By default, symbol table variables and numeric constants
  336. are assigned the format code
  337. <TT>'X'</TT>
  338. which specifies 32-bit hexadecimal.
  339. Printing such a variable yields output of the form
  340. <TT>0x00123456</TT>.
  341. An indirect reference through the variable fetches 32 bits
  342. of data at the address indicated by the variable.
  343. Other formats specify various data types, for example
  344. <TT>i</TT>
  345. an instruction,
  346. <TT>D</TT>
  347. a signed 32 bit decimal,
  348. <TT>s</TT>
  349. a null-terminated string.
  350. The
  351. <TT>fmt</TT>
  352. function
  353. allows the user to change the format code of a variable
  354. to control the printing format and
  355. operator side effects.
  356. This function evaluates the expression supplied as the first
  357. argument, attaches the format code supplied as the second
  358. argument to the result and returns that value.
  359. If the result is assigned to a variable,
  360. the new format code applies to
  361. that variable. For convenience, Acid provides the
  362. <TT>o</TT>
  363. perator as a shorthand infix form of
  364. <TT>fmt</TT>.
  365. For example:
  366. <DL><DT><DD><TT><PRE>
  367. acid: x=10
  368. acid: x // print x in hex
  369. 0x0000000a
  370. acid: x = fmt(x, 'D') // make x type decimal
  371. acid: print(x, fmt(x, 'X'), x\X) // print x in decimal &amp; hex
  372. 10 0x0000000a 0x0000000a
  373. acid: x // print x in decimal
  374. 10
  375. acid: x\o // print x in octal
  376. 000000000012
  377. </PRE></TT></DL>
  378. The
  379. <TT>++</TT>
  380. and
  381. <TT>--</TT>
  382. operators increment or decrement a variable by an amount
  383. determined by its format code. Some formats imply a non-fixed size.
  384. For example, the
  385. <TT>i</TT>
  386. format code disassembles an instruction into a string.
  387. On a 68020, which has variable length instructions:
  388. <DL><DT><DD><TT><PRE>
  389. acid: p=main\i // p=addr(main), type INST
  390. acid: loop 1,5 do print(p\X, @p++) // disassemble 5 instr's
  391. 0x0000222e LEA 0xffffe948(A7),A7
  392. 0x00002232 MOVL s+0x4(A7),A2
  393. 0x00002236 PEA 0x2f($0)
  394. 0x0000223a MOVL A2,-(A7)
  395. 0x0000223c BSR utfrrune
  396. acid:
  397. </PRE></TT></DL>
  398. Here,
  399. <TT>main</TT>
  400. is the address of the function of the same name in the program under test.
  401. The loop retrieves the five instructions beginning at that address and
  402. then prints the address and the assembly language representation of each.
  403. Notice that the stride of the increment operator varies with the size of
  404. the instruction: the
  405. <TT>MOVL</TT>
  406. at
  407. <TT>0x0000223a</TT>
  408. is a two byte instruction while all others are four bytes long.
  409. </P>
  410. <P>
  411. Registers are treated as normal program variables referenced
  412. by their symbolic assembler language names.
  413. When a
  414. process stops, the register set is saved by the kernel
  415. at a known virtual address in the process memory map.
  416. The Acid variables associated with the registers point
  417. to the saved values and the
  418. <TT>*</TT>
  419. indirection operator can then be used to read and write the register set.
  420. Since the registers are accessed via Acid variables they may
  421. be used in arbitrary expressions.
  422. <DL><DT><DD><TT><PRE>
  423. acid: PC // addr of saved PC
  424. 0xc0000f60
  425. acid: *PC
  426. 0x0000623c // contents of PC
  427. acid: *PC\a
  428. main
  429. acid: *R1=10 // modify R1
  430. acid: asm(*PC+4) // disassemble @ PC+4
  431. main+0x4 0x00006240 MOVW R31,0x0(R29)
  432. main+0x8 0x00006244 MOVW $setR30(SB),R30
  433. main+0x10 0x0000624c MOVW R1,_clock(SB)
  434. </PRE></TT></DL>
  435. Here, the saved
  436. <TT>PC</TT>
  437. is stored at address
  438. <TT>0xc0000f60</TT>;
  439. its current content is
  440. <TT>0x0000623c</TT>.
  441. The
  442. `<TT>a</TT>'
  443. format code converts this value to a string specifying
  444. the address as an offset beyond the nearest symbol.
  445. After setting the value of register
  446. <TT>1</TT>,
  447. the example uses the
  448. <TT>asm</TT>
  449. command to disassemble a short section of code beginning
  450. at four bytes beyond the current value of the
  451. <TT>PC</TT>.
  452. </P>
  453. <H4>7 Process Interface
  454. </H4>
  455. <P>
  456. A program executing under Acid is monitored through the
  457. <I>proc</I>
  458. file system interface provided by Plan 9.
  459. Textual messages written to the
  460. <TT>ctl</TT>
  461. file control the execution of the process.
  462. For example writing
  463. <TT>waitstop</TT>
  464. to the control file causes the write to block until the target
  465. process enters the kernel and is stopped. When the process is stopped
  466. the write completes. The
  467. <TT>startstop</TT>
  468. message starts the target process and then does a
  469. <TT>waitstop</TT>
  470. action.
  471. Synchronization between the debugger and the target process is determined
  472. by the actions of the various messages. Some operate asynchronously to the
  473. target process and always complete immediately, others block until the
  474. action completes. The asynchronous messages allow Acid to control
  475. several processes simultaneously.
  476. </P>
  477. <P>
  478. The interpreter has builtin functions named after each of the control
  479. messages. The functions take a process id as argument.
  480. Any time a control message causes the program to execute instructions
  481. the interpreter performs two actions when the control operation has completed.
  482. The Acid variables pointing at the register set are fixed up to point
  483. at the saved registers, and then
  484. the user defined function
  485. <TT>stopped</TT>
  486. is executed.
  487. The
  488. <TT>stopped</TT>
  489. function may print the current address,
  490. line of source or instruction and return to interactive mode. Alternatively
  491. it may traverse a complex data structure, gather statistics and then set
  492. the program running again.
  493. </P>
  494. <P>
  495. Several Acid variables are maintained by the debugger rather than the
  496. programmer.
  497. These variables allow generic Acid code to deal with the current process,
  498. architecture specifics or the symbol table.
  499. The variable
  500. <TT>pid</TT>
  501. is the process id of the current process Acid is debugging.
  502. The variable
  503. <TT>symbols</TT>
  504. contains a list of lists where each sublist contains the symbol
  505. name, its type and the value of the symbol.
  506. The variable
  507. <TT>registers</TT>
  508. contains a list of the machine-specific register names. Global symbols in the target program
  509. can be referenced directly by name from Acid. Local variables
  510. are referenced using the colon operator as <TT>function:variable</TT>.
  511. </P>
  512. <H4>8 Source Level Debugging
  513. </H4>
  514. <P>
  515. Acid provides several builtin functions to manipulate source code.
  516. The
  517. <TT>file</TT>
  518. function reads a text file, inserting each line into a list.
  519. The
  520. <TT>pcfile</TT>
  521. and
  522. <TT>pcline</TT>
  523. functions each take an address as an argument.
  524. The first
  525. returns a string containing the name of the source file
  526. and the second returns an integer containing the line number
  527. of the source line containing the instruction at the address.
  528. <DL><DT><DD><TT><PRE>
  529. acid: pcfile(main) // file containing main
  530. main.c
  531. acid: pcline(main) // line # of main in source
  532. 11
  533. acid: file(pcfile(main))[pcline(main)] // print that line
  534. main(int argc, char *argv[])
  535. acid: src(*PC) // print statements nearby
  536. 9
  537. 10 void
  538. &#62;11 main(int argc, char *argv[])
  539. 12 {
  540. 13 int a;
  541. </PRE></TT></DL>
  542. In this example, the three primitives are combined in an expression to print
  543. a line of source code associated with an address.
  544. The
  545. <TT>src</TT>
  546. function prints a few lines of source
  547. around the address supplied as its argument. A companion routine,
  548. <TT>Bsrc</TT>,
  549. communicates with the external editor
  550. <TT>sam</TT>.
  551. Given an address, it loads the corresponding source file into the editor
  552. and highlights the line containing the address. This simple interface
  553. is easily extended to more complex functions.
  554. For example, the
  555. <TT>step</TT>
  556. function can select the current file and line in the editor
  557. each time the target program stops, giving the user a visual
  558. trace of the execution path of the program. A more complete interface
  559. allowing two way communication between Acid and the
  560. <TT>acme</TT>
  561. user interface [Pike93] is under construction. A filter between the debugger
  562. and the user interface provides interpretation of results from both
  563. sides of the interface. This allows the programming environment to
  564. interact with the debugger and vice-versa, a capability missing from the
  565. <TT>sam</TT>
  566. interface.
  567. The
  568. <TT>src</TT>
  569. and
  570. <TT>Bsrc</TT>
  571. functions are both written in Acid code using the file and line primitives.
  572. Acid provides library functions to step through source level
  573. statements and functions. Furthermore, addresses in Acid expressions can be
  574. specified by source file and line.
  575. Source code is manipulated in the Acid
  576. <I>list</I>
  577. data type.
  578. </P>
  579. <H4>9 The Acid Library
  580. </H4>
  581. <P>
  582. The following examples define some useful commands and
  583. illustrate the interaction of the debugger and the interpreter.
  584. <DL><DT><DD><TT><PRE>
  585. defn bpset(addr) // set breakpoint
  586. {
  587. if match(addr, bplist) &#62;= 0 then
  588. print("bkpoint already set:", addr\a, "\n");
  589. else {
  590. *fmt(addr, bpfmt) = bpinst; // plant it
  591. bplist = append bplist, addr; // add to list
  592. }
  593. }
  594. </PRE></TT></DL>
  595. The
  596. <TT>bpset</TT>
  597. function plants a break point in memory. The function starts by
  598. using the
  599. <TT>match</TT>
  600. builtin to
  601. search the breakpoint list to determine if a breakpoint is already
  602. set at the address.
  603. The indirection operator, controlled by the format code returned
  604. by the
  605. <TT>fmt</TT>
  606. primitive, is used to plant the breakpoint in memory.
  607. The variables
  608. <TT>bpfmt</TT>
  609. and
  610. <TT>bpinst</TT>
  611. are Acid global variables containing the format code specifying
  612. the size of the breakpoint instruction and the breakpoint instruction
  613. itself.
  614. These
  615. variables are set by architecture-dependent library code
  616. when the debugger first attaches to the executing image.
  617. Finally the address of the breakpoint is
  618. appended to the breakpoint list,
  619. <TT>bplist</TT>.
  620. <DL><DT><DD><TT><PRE>
  621. defn step() // single step
  622. {
  623. local lst, lpl, addr, bput;
  624. bput = 0; // sitting on bkpoint
  625. if match(*PC, bplist) &#62;= 0 then {
  626. bput = fmt(*PC, bpfmt); // save current addr
  627. *bput = @bput; // replace it
  628. }
  629. lst = follow(*PC); // get follow set
  630. lpl = lst;
  631. while lpl do { // place breakpoints
  632. *(head lpl) = bpinst;
  633. lpl = tail lpl;
  634. }
  635. startstop(pid); // do the step
  636. while lst do { // remove breakpoints
  637. addr = fmt(head lst, bpfmt);
  638. *addr = @addr; // replace instr.
  639. lst = tail lst;
  640. }
  641. if bput != 0 then
  642. *bput = bpinst; // restore breakpoint
  643. }
  644. </PRE></TT></DL>
  645. The
  646. <TT>step</TT>
  647. function executes a single assembler instruction.
  648. If the
  649. <TT>PC</TT>
  650. is sitting
  651. on a breakpoint, the address and size of
  652. the breakpoint are saved.
  653. The breakpoint instruction
  654. is then removed using the
  655. <TT>@</TT>
  656. operator to fetch
  657. <TT>bpfmt</TT>
  658. bytes from the text file and to place it into the memory
  659. of the executing process using the
  660. <TT>*</TT>
  661. operator.
  662. The
  663. <TT>follow</TT>
  664. function is an Acid
  665. builtin which returns a follow-set: a list of instruction addresses which
  666. could be executed next.
  667. If the instruction stored at the
  668. <TT>PC</TT>
  669. is a branch instruction, the
  670. list contains the addresses of the next instruction and
  671. the branch destination; otherwise, it contains only the
  672. address of the next instruction.
  673. The follow-set is then used to replace each possible following
  674. instruction with a breakpoint instruction. The original
  675. instructions need not be saved; they remain
  676. in their unaltered state in the text file.
  677. The
  678. <TT>startstop</TT>
  679. builtin writes the `startstop' message to the
  680. <I>proc</I>
  681. control file for the process named
  682. <TT>pid</TT>.
  683. The target process executes until some condition causes it to
  684. enter the kernel, in this case, the execution of a breakpoint.
  685. When the process blocks, the debugger regains control and invokes the
  686. Acid library function
  687. <TT>stopped</TT>
  688. which reports the address and cause of the blockage.
  689. The
  690. <TT>startstop</TT>
  691. function completes and returns to the
  692. <TT>step</TT>
  693. function where
  694. the follow-set is used to replace the breakpoints placed earlier.
  695. Finally, if the address of the original
  696. <TT>PC</TT>
  697. contained a breakpoint, it is replaced.
  698. </P>
  699. <P>
  700. Notice that this approach to process control is inherently portable;
  701. the Acid code is shared by the debuggers for all architectures.
  702. Acid variables and builtin functions provide a transparent interface
  703. to architecture-dependent values and functions. Here the breakpoint
  704. value and format are referenced through Acid variables and the
  705. <TT>follow</TT>
  706. primitive masks the differences in the underlying instruction set.
  707. </P>
  708. <P>
  709. The
  710. <TT>next</TT>
  711. function, similar to the
  712. <I>dbx</I>
  713. command of the same name,
  714. is a simpler example.
  715. This function steps through
  716. a single source statement but steps over function calls.
  717. <DL><DT><DD><TT><PRE>
  718. defn next()
  719. {
  720. local sp, bound;
  721. sp = *SP; // save starting SP
  722. bound = fnbound(*PC); // begin &amp; end of fn.
  723. stmnt(); // step 1 statement
  724. pc = *PC;
  725. if pc &#62;= bound[0] &amp;&amp; pc &#60; bound[1] then
  726. return {};
  727. while (pc&#60;bound[0] || pc&#62;bound[1]) &amp;&amp; sp&#62;=*SP do {
  728. step();
  729. pc = *PC;
  730. }
  731. src(*PC);
  732. }
  733. </PRE></TT></DL>
  734. The
  735. <TT>next</TT>
  736. function
  737. starts by saving the current stack pointer in a local variable.
  738. It then uses the Acid library function
  739. <TT>fnbound</TT>
  740. to return the addresses of the first and last instructions in
  741. the current function in a list.
  742. The
  743. <TT>stmnt</TT>
  744. function executes a single source statement and then uses
  745. <TT>src</TT>
  746. to print a few lines of source around the new
  747. <TT>PC</TT>.
  748. If the new value of the
  749. <TT>PC</TT>
  750. remains in the current function,
  751. <TT>next</TT>
  752. returns.
  753. When the executed statement is a function call or a return
  754. from a function, the new value of the
  755. <TT>PC</TT>
  756. is outside the bounds calculated by
  757. <TT>fnbound</TT>
  758. and the test of the
  759. <TT>while</TT>
  760. loop is evaluated.
  761. If the statement was a return, the new value of the stack pointer
  762. is greater than the original value and the loop completes without
  763. execution.
  764. Otherwise, the loop is entered and instructions are continually
  765. executed until the value of the
  766. <TT>PC</TT>
  767. is between the bounds calculated earlier. At that point, execution
  768. ceases and a few lines of source in the vicinity of the
  769. <TT>PC</TT>
  770. are printed.
  771. </P>
  772. <P>
  773. Acid provides concise and elegant expression for control and
  774. manipulation of target programs. These examples demonstrate how a
  775. few well-chosen primitives can be combined to create a rich debugging environment.
  776. </P>
  777. <H4>10 Dealing With Multiple Architectures
  778. </H4>
  779. <P>
  780. A single binary of Acid may be used to debug a program running on any
  781. of the five processor architectures supported by Plan 9. For example,
  782. Plan 9 allows a user on a MIPS to import the
  783. <I>proc</I>
  784. file system from an i486-based PC and remotely debug a program executing
  785. on that processor.
  786. </P>
  787. <P>
  788. Two levels of abstraction provide this architecture independence.
  789. On the lowest level, a Plan 9 library supplies functions to
  790. decode the file header of the program being debugged and
  791. select a table of system parameters
  792. and a jump vector of architecture-dependent
  793. functions based on the magic number.
  794. Among these functions are byte-order-independent
  795. access to memory and text files, stack manipulation, disassembly,
  796. and floating point number interpretation.
  797. The second level of abstraction is supplied by Acid.
  798. It consists of primitives and approximately 200 lines
  799. of architecture-dependent Acid library code that interface the
  800. interpreter to the architecture-dependent library.
  801. This layer performs functions such as mapping register names to
  802. memory locations, supplying breakpoint values and sizes,
  803. and converting processor specific data to Acid data types.
  804. An example of the latter is the stack trace function
  805. <TT>strace</TT>,
  806. which uses the stack traversal functions in the
  807. architecture-dependent library to construct a list of lists describing
  808. the context of a process. The first level of list selects
  809. each function in the trace; subordinate lists contain the
  810. names and values of parameters and local variables of
  811. the functions. Acid commands and library functions that
  812. manipulate and display process state information operate
  813. on the list representation and are independent of the
  814. underlying architecture.
  815. </P>
  816. <H4>11 Alef Runtime
  817. </H4>
  818. <P>
  819. Alef is a concurrent programming language,
  820. designed specifically for systems programming, which supports both
  821. shared variable and message passing paradigms.
  822. Alef borrows the C expression syntax but implements
  823. a substantially different type system.
  824. The language provides a rich set of
  825. exception handling, process management, and synchronization
  826. primitives, which rely on a runtime system.
  827. Alef program bugs are often deadlocks, synchronization failures,
  828. or non-termination caused by locks being held incorrectly.
  829. In such cases, a process stalls deep
  830. in the runtime code and it is clearly
  831. unreasonable to expect a programmer using the language
  832. to understand the detailed
  833. internal semantics of the runtime support functions.
  834. </P>
  835. <P>
  836. Instead, there is an Alef support library, coded in Acid, that
  837. allows the programmer to interpret the program state in terms of
  838. Alef operations. Consider the example of a multi-process program
  839. stalling because of improper synchronization. A stack trace of
  840. the program indicates that it is waiting for an event in some
  841. obscure Alef runtime
  842. synchronization function.
  843. The function itself is irrelevant to the
  844. programmer; of greater importance is the identity of the
  845. unfulfilled event.
  846. Commands in the Alef support library decode
  847. the runtime data structures and program state to report the cause
  848. of the blockage in terms of the high-level operations available to
  849. the Alef programmer.
  850. Here, the Acid language acts
  851. as a communications medium between Alef implementer and Alef user.
  852. </P>
  853. <H4>12 Parallel Debugging
  854. </H4>
  855. <P>
  856. The central issue in parallel debugging is how the debugger is
  857. multiplexed between the processes comprising
  858. the program.
  859. Acid has no intrinsic model of process partitioning; it
  860. only assumes that parallel programs share a symbol table,
  861. though they need not share memory.
  862. The
  863. <TT>setproc</TT>
  864. primitive attaches the debugger to a running process
  865. associated with the process ID supplied as its argument
  866. and assigns that value to the global variable
  867. <TT>pid</TT>,
  868. thereby allowing simple rotation among a group of processes.
  869. Further, the stack trace primitive is driven by parameters
  870. specifying a unique process context, so it is possible to
  871. examine the state of cooperating processes without switching
  872. the debugger focus from the process of interest.
  873. Since Acid is inherently extensible and capable of
  874. dynamic interaction with subordinate processes, the
  875. programmer can define Acid commands to detect and control
  876. complex interactions between processes.
  877. In short, the programmer is free to specify how the debugger reacts
  878. to events generated in specific threads of the program.
  879. </P>
  880. <P>
  881. The support for parallel debugging in Acid depends on a crucial kernel
  882. modification: when the text segment of a program is written (usually to
  883. place a breakpoint), the segment is cloned to prevent other threads
  884. from encountering the breakpoint. Although this incurs a slight performance
  885. penalty, it is of little importance while debugging.
  886. </P>
  887. <H4>13 Communication Between Tools
  888. </H4>
  889. <P>
  890. The Plan 9 Alef and C compilers do not
  891. embed detailed type information in the symbol table of an
  892. executable file.
  893. However, they do accept a command line option causing them to
  894. emit descriptions of complex data types
  895. (e.g., aggregates and abstract data types)
  896. to an auxiliary file.
  897. The vehicle for expressing this information is Acid source code.
  898. When an Acid debugging session is
  899. subsequently started, that file is loaded with the other Acid libraries.
  900. </P>
  901. <P>
  902. For each complex object in the program the compiler generates
  903. three pieces of Acid code.
  904. The first is a table describing the size and offset of each
  905. member of the complex data type. Following is an Acid function,
  906. named the same as the object, that formats and prints each member.
  907. Finally, Acid declarations associate the
  908. Alef or C program variables of a type with the functions
  909. to print them.
  910. The three forms of declaration are shown in the following example:
  911. <DL><DT><DD><TT><PRE>
  912. struct Bitmap {
  913. Rectangle 0 r;
  914. Rectangle 16 clipr;
  915. 'D' 32 ldepth;
  916. 'D' 36 id;
  917. 'X' 40 cache;
  918. };
  919. </PRE></TT></DL>
  920. <DL><DT><DD><TT><PRE>
  921. defn
  922. Bitmap(addr) {
  923. complex Bitmap addr;
  924. print("Rectangle r {\n");
  925. Rectangle(addr.r);
  926. print("}\n");
  927. print("Rectangle clipr {\n");
  928. Rectangle(addr.clipr);
  929. print("}\n");
  930. print(" ldepth ", addr.ldepth, "\n");
  931. print(" id ", addr.id, "\n");
  932. print(" cache ", addr.cache, "\n");
  933. };
  934. complex Bitmap darkgrey;
  935. complex Bitmap Window_settag:b;
  936. </PRE></TT></DL>
  937. The
  938. <TT>struct</TT>
  939. declaration specifies decoding instructions for the complex type named
  940. <TT>Bitmap</TT>.
  941. Although the syntax is superficially similar to a C structure declaration,
  942. the semantics differ markedly: the C declaration specifies a layout, while
  943. the Acid declaration tells how to decode it.
  944. The declaration specifies a type, an offset, and name for each
  945. member of the complex object. The type is either the name of another
  946. complex declaration, for example,
  947. <TT>Rectangle</TT>,
  948. or a format code.
  949. The offset is the number of bytes from the start
  950. of the object to the member
  951. and the name is the member's name in the Alef or C declaration.
  952. This type description is a close match for C and Alef, but is simple enough
  953. to be language independent.
  954. </P>
  955. <P>
  956. The
  957. <TT>Bitmap</TT>
  958. function expects the address of a
  959. <TT>Bitmap</TT>
  960. as its only argument.
  961. It uses the decoding information contained in the
  962. <TT>Bitmap</TT>
  963. structure declaration to extract, format, and print the
  964. value of each member of the complex object pointed to by
  965. the argument.
  966. The Alef compiler emits code to call other Acid functions
  967. where a member is another complex type; here,
  968. <TT>Bitmap</TT>
  969. calls
  970. <TT>Rectangle</TT>
  971. to print its contents.
  972. </P>
  973. <P>
  974. The
  975. <TT>complex</TT>
  976. declarations associate Alef variables with complex types.
  977. In the example,
  978. <TT>darkgrey</TT>
  979. is the name of a global variable of type
  980. <TT>Bitmap</TT>
  981. in the program being debugged.
  982. Whenever the name
  983. <TT>darkgrey</TT>
  984. is evaluated by Acid, it automatically calls the
  985. <TT>Bitmap</TT>
  986. function with the address of
  987. <TT>darkgrey</TT>
  988. as the argument.
  989. The second
  990. <TT>complex</TT>
  991. declaration associates a local variable or parameter named
  992. <TT>b</TT>
  993. in function
  994. <TT>Window_settag</TT>
  995. with the
  996. <TT>Bitmap</TT>
  997. complex data type.
  998. </P>
  999. <P>
  1000. Acid borrows the C operators
  1001. <TT>.</TT>
  1002. and
  1003. <TT>-></TT>
  1004. to access the decoding parameters of a member of a complex type.
  1005. Although this representation is sufficiently general for describing
  1006. the decoding of both C and Alef complex data types, it may
  1007. prove too restrictive for target languages with more complicated
  1008. type systems.
  1009. Further, the assumption that the compiler can select the proper
  1010. Acid format code for each basic type in the language is somewhat
  1011. naive. For example, when a member of a complex type is a pointer,
  1012. it is assigned a hexadecimal type code; integer members are always
  1013. assigned a decimal type code.
  1014. This heuristic proves inaccurate when an integer field is a
  1015. bit mask or set of bit flags which are more appropriately displayed
  1016. in hexadecimal or octal.
  1017. </P>
  1018. <H4>14 Code Verification
  1019. </H4>
  1020. <P>
  1021. Acid's ability to interact dynamically with
  1022. an executing program allows passive test and
  1023. verification of the target program. For example,
  1024. a common concern is leak detection in programs using
  1025. <TT>malloc</TT>.
  1026. Of interest are two items: finding memory that was allocated
  1027. but never freed and detecting bad pointers passed to
  1028. <TT>free</TT>.
  1029. An auxiliary Acid library contains Acid functions to
  1030. monitor the execution of a program and detect these
  1031. faults, either as they happen or in the automated
  1032. post-mortem analysis of the memory arena.
  1033. In the following example, the
  1034. <TT>sort</TT>
  1035. command is run under the control of the
  1036. Acid memory leak library.
  1037. <DL><DT><DD><TT><PRE>
  1038. helix% acid -l malloc /bin/sort
  1039. /bin/sort: mips plan 9 executable
  1040. /lib/acid/port
  1041. /lib/acid/mips
  1042. /lib/acid/malloc
  1043. acid: go()
  1044. now
  1045. is
  1046. the
  1047. time
  1048. &#60;ctrl-d&#62;
  1049. is
  1050. now
  1051. the
  1052. time
  1053. 27680 : breakpoint _exits+0x4 MOVW $0x8,R1
  1054. acid:
  1055. </PRE></TT></DL>
  1056. The
  1057. <TT>go</TT>
  1058. command creates a process and plants
  1059. breakpoints at the entry to
  1060. <TT>malloc</TT>
  1061. and
  1062. <TT>free</TT>.
  1063. The program is then started and continues until it
  1064. exits or stops. If the reason for stopping is anything
  1065. other than the breakpoints in
  1066. <TT>malloc</TT>
  1067. and
  1068. <TT>free</TT>,
  1069. Acid prints the usual status information and returns to the
  1070. interactive prompt.
  1071. </P>
  1072. <P>
  1073. When the process stops on entering
  1074. <TT>malloc</TT>,
  1075. the debugger must capture and save the address that
  1076. <TT>malloc</TT>
  1077. will return.
  1078. After saving a stack
  1079. trace so the calling routine can be identified, it places
  1080. a breakpoint at the return address and restarts the program.
  1081. When
  1082. <TT>malloc</TT>
  1083. returns, the breakpoint stops the program,
  1084. allowing the debugger
  1085. to grab the address of the new memory block from the return register.
  1086. The address and stack trace are added to the list of outstanding
  1087. memory blocks, the breakpoint is removed from the return point, and
  1088. the process is restarted.
  1089. </P>
  1090. <P>
  1091. When the process stops at the beginning of
  1092. <TT>free</TT>,
  1093. the memory address supplied as the argument is compared to the list
  1094. of outstanding memory blocks. If it is not found an error message
  1095. and a stack trace of the call is reported; otherwise, the
  1096. address is deleted from the list.
  1097. </P>
  1098. <P>
  1099. When the program exits, the list of outstanding memory blocks contains
  1100. the addresses of all blocks that were allocated but never freed.
  1101. The
  1102. <TT>leak</TT>
  1103. library function traverses the list producing a report describing
  1104. the allocated blocks.
  1105. <DL><DT><DD><TT><PRE>
  1106. acid: leak()
  1107. Lost a total of 524288 bytes from:
  1108. malloc() malloc.c:32 called from dofile+0xe8 sort.c:217
  1109. dofile() sort.c:190 called from main+0xac sort.c:161
  1110. main() sort.c:128 called from _main+0x20 main9.s:10
  1111. Lost a total of 64 bytes from:
  1112. malloc() malloc.c:32 called from newline+0xfc sort.c:280
  1113. newline() sort.c:248 called from dofile+0x110 sort.c:222
  1114. dofile() sort.c:190 called from main+0xac sort.c:161
  1115. main() sort.c:128 called from _main+0x20 main9.s:10
  1116. Lost a total of 64 bytes from:
  1117. malloc() malloc.c:32 called from realloc+0x14 malloc.c:129
  1118. realloc() malloc.c:123 called from bldkey+0x358 sort.c:1388
  1119. buildkey() sort.c:1345 called from newline+0x150 sort.c:285
  1120. newline() sort.c:248 called from dofile+0x110 sort.c:222
  1121. dofile() sort.c:190 called from main+0xac sort.c:161
  1122. main() sort.c:128 called from _main+0x20 main9.s:10
  1123. acid: refs()
  1124. data...bss...stack...
  1125. acid: leak()
  1126. acid:
  1127. </PRE></TT></DL>
  1128. The presence of a block in the allocation list does not imply
  1129. it is there because of a leak; for instance, it may have been
  1130. in use when the program terminated.
  1131. The
  1132. <TT>refs()</TT>
  1133. library function scans the
  1134. <I>data</I>,
  1135. <I>bss</I>,
  1136. and
  1137. <I>stack</I>
  1138. segments of the process looking for pointers
  1139. into the allocated blocks. When one is found, the block is deleted from
  1140. the outstanding block list.
  1141. The
  1142. <TT>leak</TT>
  1143. function is used again to report the
  1144. blocks remaining allocated and unreferenced.
  1145. This strategy proves effective in detecting
  1146. disconnected (but non-circular) data structures.
  1147. </P>
  1148. <P>
  1149. The leak detection process is entirely passive.
  1150. The program is not
  1151. specially compiled and the source code is not required.
  1152. As with the Acid support functions for the Alef runtime environment,
  1153. the author of the library routines has encapsulated the
  1154. functionality of the library interface
  1155. in Acid code.
  1156. Any programmer may then check a program's use of the
  1157. library routines without knowledge of either implementation.
  1158. The performance impact of running leak detection is great
  1159. (about 10 times slower),
  1160. but it has not prevented interactive programs like
  1161. <TT>sam</TT>
  1162. and the
  1163. <TT>8&#189;</TT>
  1164. window system from being tested.
  1165. </P>
  1166. <H4>15 Code Coverage
  1167. </H4>
  1168. <P>
  1169. Another common component of software test uses
  1170. <I>coverage</I>
  1171. analysis.
  1172. The purpose of the test is to determine which paths through the code have
  1173. not been executed while running the test suite.
  1174. This is usually
  1175. performed by a combination of compiler support and a reporting tool run
  1176. on the output generated by statements compiled into the program.
  1177. The compiler emits code that
  1178. logs the progress of the program as it executes basic blocks and writes the
  1179. results to a file. The file is then processed by the reporting tool
  1180. to determine which basic blocks have not been executed.
  1181. </P>
  1182. <P>
  1183. Acid can perform the same function in a language independent manner without
  1184. modifying the source, object or binary of the program. The following example
  1185. shows
  1186. <TT>ls</TT>
  1187. being run under the control of the Acid coverage library.
  1188. <DL><DT><DD><TT><PRE>
  1189. philw-helix% acid -l coverage /bin/ls
  1190. /bin/ls: mips plan 9 executable
  1191. /lib/acid/port
  1192. /lib/acid/mips
  1193. /lib/acid/coverage
  1194. acid: coverage()
  1195. acid
  1196. newstime
  1197. profile
  1198. tel
  1199. wintool
  1200. 2: (error) msg: pid=11419 startstop: process exited
  1201. acid: analyse(ls)
  1202. ls.c:102,105
  1203. 102: return 1;
  1204. 103: }
  1205. 104: if(db[0].qid.path&amp;CHDIR &amp;&amp; dflag==0){
  1206. 105: output();
  1207. ls.c:122,126
  1208. 122: memmove(dirbuf+ndir, db, sizeof(Dir));
  1209. 123: dirbuf[ndir].prefix = 0;
  1210. 124: p = utfrrune(s, '/');
  1211. 125: if(p){
  1212. 126: dirbuf[ndir].prefix = s;
  1213. </PRE></TT></DL>
  1214. The
  1215. <TT>coverage</TT>
  1216. function begins by looping through the text segment placing
  1217. breakpoints at the entry to each basic block. The start of each basic
  1218. block is found using the Acid builtin function
  1219. <TT>follow</TT>.
  1220. If the list generated by
  1221. <TT>follow</TT>
  1222. contains more than one
  1223. element, then the addresses mark the start of basic blocks. A breakpoint
  1224. is placed at each address to detect entry into the block. If the result
  1225. of
  1226. <TT>follow</TT>
  1227. is a single address then no action is taken, and the next address is
  1228. considered. Acid maintains a list of
  1229. breakpoints already in place and avoids placing duplicates (an address may be
  1230. the destination of several branches).
  1231. </P>
  1232. <P>
  1233. After placing the breakpoints the program is set running.
  1234. Each time a breakpoint is encountered
  1235. Acid deletes the address from the breakpoint list, removes the breakpoint
  1236. from memory and then restarts the program.
  1237. At any instant the breakpoint list contains the addresses of basic blocks
  1238. which have not been executed.
  1239. The
  1240. <TT>analyse</TT>
  1241. function reports the lines of source code bounded by basic blocks
  1242. whose addresses are have not been deleted from the breakpoint list.
  1243. These are the basic blocks which have not been executed.
  1244. Program performance is almost unaffected since each breakpoint is executed
  1245. only once and then removed.
  1246. </P>
  1247. <P>
  1248. The library contains a total of 128 lines of Acid code.
  1249. An obvious extension of this algorithm could be used to provide basic block
  1250. profiling.
  1251. </P>
  1252. <H4>16 Conclusion
  1253. </H4>
  1254. <P>
  1255. Acid has two areas of weakness. As with
  1256. other language-based tools like
  1257. <I>awk</I>,
  1258. a programmer must learn yet another language to step beyond the normal
  1259. debugging functions and use the full power of the debugger.
  1260. Second, the command line interface supplied by the
  1261. <I>yacc</I>
  1262. parser is inordinately clumsy.
  1263. Part of the problem relates directly to the use of
  1264. <I>yacc</I>
  1265. and could be circumvented with a custom parser.
  1266. However, structural problems would remain: Acid often requires
  1267. too much typing to execute a simple
  1268. command.
  1269. A debugger should prostitute itself to its users, doing whatever
  1270. is wanted with a minimum of encouragement; commands should be
  1271. concise and obvious. The language interface is more consistent than
  1272. an ad hoc command interface but is clumsy to use.
  1273. Most of these problems are addressed by an Acme interface
  1274. which is under construction. This should provide the best of
  1275. both worlds: graphical debugging and access to the underlying acid
  1276. language when required.
  1277. </P>
  1278. <P>
  1279. The name space clash between Acid variables, keywords, program variables,
  1280. and functions is unavoidable.
  1281. Although it rarely affects a debugging session, it is annoying
  1282. when it happens and is sometimes difficult to circumvent.
  1283. The current renaming scheme
  1284. is too crude; the new names are too hard to remember.
  1285. </P>
  1286. <P>
  1287. Acid has proved to be a powerful tool whose applications
  1288. have exceeded expectations.
  1289. Of its strengths, portability, extensibility and parallel debugging support
  1290. were by design and provide the expected utility.
  1291. In retrospect,
  1292. its use as a tool for code test and verification and as
  1293. a medium for communicating type information and encapsulating
  1294. interfaces has provided unanticipated benefits and altered our
  1295. view of the debugging process.
  1296. </P>
  1297. <H4>17 Acknowledgments
  1298. </H4>
  1299. <P>
  1300. Bob Flandrena was the first user and helped prepare the paper.
  1301. Rob Pike endured three buggy Alef compilers and a new debugger
  1302. in a single sitting.
  1303. </P>
  1304. <H4>18 References
  1305. </H4>
  1306. <br>&#32;<br>
  1307. [Pike90] R. Pike, D. Presotto, K. Thompson, H. Trickey,
  1308. ``Plan 9 from Bell Labs'',
  1309. UKUUG Proc. of the Summer 1990 Conf.,
  1310. London, England,
  1311. 1990,
  1312. reprinted, in a different form, in this volume.
  1313. <br>&#32;<br>
  1314. [Gol93] M. Golan, D. Hanson,
  1315. ``DUEL -- A Very High-Level Debugging Language'',
  1316. USENIX Proc. of the Winter 1993 Conf.,
  1317. San Diego, CA,
  1318. 1993.
  1319. <br>&#32;<br>
  1320. [Lin90] M. A. Linton,
  1321. ``The Evolution of DBX'',
  1322. USENIX Proc. of the Summer 1990 Conf.,
  1323. Anaheim, CA,
  1324. 1990.
  1325. <br>&#32;<br>
  1326. [Stal91] R. M. Stallman, R. H. Pesch,
  1327. ``Using GDB: A guide to the GNU source level debugger'',
  1328. Technical Report, Free Software Foundation,
  1329. Cambridge, MA,
  1330. 1991.
  1331. <br>&#32;<br>
  1332. [Win93] P. Winterbottom,
  1333. ``Alef reference Manual'',
  1334. this volume.
  1335. <br>&#32;<br>
  1336. [Pike93] Rob Pike,
  1337. ``Acme: A User Interface for Programmers'',
  1338. USENIX Proc. of the Winter 1994 Conf.,
  1339. San Francisco, CA,
  1340. reprinted in this volume.
  1341. <br>&#32;<br>
  1342. [Ols90] Ronald A. Olsson, Richard H. Crawford, and W. Wilson Ho,
  1343. ``Dalek: A GNU, improved programmable debugger'',
  1344. USENIX Proc. of the Summer 1990 Conf.,
  1345. Anaheim, CA.
  1346. <br>&#32;<br>
  1347. [May92] Paul Maybee,
  1348. ``NeD: The Network Extensible Debugger''
  1349. USENIX Proc. of the Summer 1992 Conf.,
  1350. San Antonio, TX.
  1351. <br>&#32;<br>
  1352. [Aral] Ziya Aral, Ilya Gertner, and Greg Schaffer,
  1353. ``Efficient debugging primitives for multiprocessors'',
  1354. Proceedings of the Third International Conference on Architectural
  1355. Support for Programming Languages and Operating Systems,
  1356. SIGPLAN notices Nr. 22, May 1989.
  1357. <br>&#32;<br>
  1358. <A href=http://www.lucent.com/copyright.html>
  1359. Copyright</A> &#169; 2000 Lucent Technologies Inc. All rights reserved.
  1360. </body></html>