Test-Driven Development of Concurrent Programs using Concuerror
Contents
1. Having briefly discussed the characteristics of our tool let us now see how Concuerror can be used in practice to detect subtle concurrency errors 4 An Extended Example 4 1 Getting started We intend to use Concuerror in a test driven development process that involves the creation of a generic registration server that can for example be used to manage limited system resources The desired functionality includes start ing and stopping the server as well as attaching and de taching processes to it However only a limited number of processes are allowed to be attached to the server at any moment First we create two Erlang modules one to contain the server code reg_server the other to contain the tests reg_server_tests Let us start by writing a start 0 function for starting the server and a trivial test that checks that the function returns ok As some EUnit assertion macros can be readily used in Concuerror tests we will use one of them namely assertEqual to check the return value of start 0 This macro tests two expressions for equality with the conven tion that the first argument declares the expected value of the second argument The reg_server_tests module shown in Test 1 uses an include_lib attribute to make this macro available Test Code 1 The initial testing module module reg_server_tests include_lib eunit include eunit hrl start_test gt assertEqual ok reg_server start Our2. self spawn fun gt Self reg_server start end spawn fun gt Self reg_server start end assertEqual lists sort already_started ok lists sort receive_two reg_server stop should observe a return value of ok and the other a return value of already_started The new test fails when run in Concuerror As seen from the detailed interleaving in formation when the two processes call whereis 1 before the server is started they both try to spawn and register the server and one of them fails with an exception Ide ally we would like the block of code containing whereis spawn and register to be executed atomically but this is currently not possible in Erlang Instead we may use the solution of allowing multiple processes to be spawned but only one of them to be prop erly registered as the server process Subsequently pro cesses that fail to be registered have to be killed To accom plish the above we use a try catch expression around the register 2 call and send a message to the spurious process forcing it to exit as shown in Program 10 Note that we cannot use a call to request 1 to kill such a pro cess because it has not been registered Our last test produces a large number of interleaving sequences thus it is preferable to start with a small pre emption bound and gradually increase it while finding and correcting any errors encountered At this point all of our tests pass with or without pre
3. Concuer ror not only allowed us to verify that our tests pass under Program 15 Detach a process as soon as it exits loop state free Free reg Reg State gt receive REG_REQUEST Target attach gt RegNum NewFreeList gt NewReg dict store Target RegNum Reg monitor process Target reply Target RegNum REG_REQUEST Target detach gt Reply NewFree NewReg detach_proc Target Free Reg reply Target Reply NewState State state free NewFree reg NewReg Loop NewState DOWN _Ref process Target Info gt NewState case dict is_key Target Reg of true gt ok NewFree NewReg detach_proc Target Free Reg State state free NewFree reg NewReg false gt State end Loop NewState end detach_proc Target Free Reg gt case dict is_key Target Reg of false gt ok Free Reg true gt RegNum dict fetch Target Reg NewReg dict erase Target Reg NewFree ordsets add_element RegNum Free ok NewFree NewReg end some random interleaving but we were guaranteed that under any interleaving our program was still robust and correct with respect to our test suite Second for all of our tests a preemption bound of two was enough to uncover any concurrency related defect It is usually convenient to start with a low preemption bound and gradually increase it for more thorough testing Third we observed the expo nential incr
4. greatly simplifies the development of certain concurrent programs and makes it significantly less error prone Still concurrent programming is fundamentally harder than its sequential counterpart Its difficulty in avoiding errors and reasoning about program correctness mainly lies in the non determinism that is introduced by unanticipated pro cess interleaving Often such interleaving results in sub tle concurrency errors which are difficult to reproduce during testing Erlang programs are not immune to such problems Tools that help programmers detect these errors early in the development process are needed in Erlang just as much as in any language Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee Erlang 11 September 23 2011 Tokyo Japan Copyright 2011 ACM 978 1 4503 0859 5 11 09 10 00 kostis it uu se To ease the systematic test driven development of con current Erlang programs we have developed Concuerror pronounced koykoror like conqueror a totally auto matic tool that given a set of tests and a program detects most kinds of concurrency related runtime er
5. ping 0 start 0 stop 0 detach gt request detach loop state free Free reg Reg State gt receive REG_REQUEST Target detach gt RegNum dict fetch Target Reg NewReg dict erase Target Reg NewFree ordsets add_element RegNum Free reply Target ok NewState State state free NewFree reg NewReg Loop NewState end Test Code 13 Test for trying to detach an unattached process detach_non_attached_test gt reg_server start assertEqual ok reg_server detach reg_server stop this we can extend the second test of Test 10 so that when one of the processes is detached another process becomes attached with the same registration number which is the only one available at the time as shown in Test 12 To make the tests pass the server needs to remove the ex isting mapping from the dictionary and add the freed reg istration number back to the set as shown in Program 13 After having successfully run our last tests and before proceeding to our final task we have to deal with one more issue namely handling the case of a process call ing detach 0 without being attached Similarly to the case of the double attach call that we encountered previ ously we can either ignore this case and return ok or con sider it an error Again we opt for the silent approach as shown in Test 13 The fix is fairly simple and is shown in Program 14 Currently an attached pr
6. be included in both the server code and the tests To be able to check if a process is attached we will extend the ping 0 function to return the calling process registration number in case it is attached to the server The attachment of two processes can be checked using the test of Test 9 We use attach to attach the calling processes to the server Function attach 0 returns the registration number that was assigned to the calling process The test also checks that the two processes are not given equal registration numbers What happens when a process calls attach while it is already attached or when the max imum number of attached processes has been reached Should a process become detached when it exits All these matters will be handled later For now let us try to make our last test pass The server can use an ordered set to keep track of the free regis tration numbers Initially this set will contain the num bers from 1 to MAX_ATTACHED Additionally the server can Program 11 Add attach 0 to the server module reg_server export attach ping 0 start 0 stop 0 include reg_server hrl record state free reg attach gt request attach start gt case whereis REG_NAME of undefined gt Pid spawn fun gt loop initState end end initState gt FreeList lists seq 1 MAX_ATTACHED state free ordsets from_list FreeList reg dict new loop state f
7. fun Pid gt Pid ok end LastProc Ps reg_server stop The server needs to know when a process exits in order to take action and detach it This means that we have to use either links or monitors to keep track of attached processes There is no reason to use two sided links here thus we will have the server create a monitor for every process that becomes attached Also as soon as the server receives a DOWN message about an attached process that process will be detached In Program 15 we implement the above functionality and move the detachment operation into a separate function to avoid code duplication At this point our final test passes successfully in Con cuerror as do all of our previous tests We do not claim that our code is entirely free of bugs However the tests that we have written check the basic functionality of our server and make us confident that any scenario that may occur in practice and has been covered by our tests will actually work as expected 5 Concluding Remarks Summing up we would like to stress some important points that came up during the presentation of our de velopment process First we quickly realized that con ventional testing using EUnit was not able to expose the concurrency errors we encountered whereas trying to test with the current version of McErlang presented some se rious usability issues Given that our server was destined to be used in a highly concurrent environment
8. heuristic pri oritization technique called preemption bounding 7 that limits the number of produced interleaving sequences ac cording to a user specified parameter Concuerror s operation can be summarized as follows The user opens the tool s graphical user interface GUI imports a number of Erlang modules and chooses a test to run As a first step Concuerror s instrumenter applies an automatic parse transformation to the imported modules in order to insert preemption points into the code After the transformed modules have been compiled and loaded the tool s scheduler executes all possible interleaving se quences of the selected test up to the chosen preemp tion bound and reports any errors encountered If the user chooses to replay an error the scheduler executes the corresponding interleaving sequence and records de tailed information about the processes actions that is then displayed in the GUI Using this information the user can iteratively apply code changes and replay the erroneous interleaving sequence to observe how program execution is affected If no errors are reported a higher preemp tion bound may be selected for a more thorough explo ration depending on the program s complexity and the user s time constraints If the test completes without de tecting any errors and the preemption bound has not been reached the program is indeed free from the kinds of con currency errors detected by the tool
9. tioned behavior we have to implement the functionality of stopping the server and use it at the end of our tests Again we leave the handling of multiple stop calls for later Program 2 Add spawn register and ping to the server Test Code 3 Stop the server at the end of our tests module reg_server export ping start 0 define REG_NAME reg_server define REG_REQUEST reg_request define REG_REPLY reg_reply start gt Pid spawn fun gt loop end register REG_NAME Pid ok ping gt REG_NAME REG_REQUEST self ping receive REG_REPLY Reply gt Reply end loop gt receive REG_REQUEST Target ping gt Target REG_REPLY pong loop end Program 3 Add stop 0 to the server module reg_server export ping 0 start 0 stop 0 stop gt REG_NAME REG_REQUEST self stop receive REG_REPLY Reply gt Reply end loop gt receive REG_REQUEST Target ping gt Target REG_REPLY pong Loop REG_REQUEST Target stop gt Target REG_REPLY ok end Function stop 0 will be used to stop the server as shown in the modified tests of Test 3 its implementation is shown in Program 3 Similarly to ping 0 a message is sent to the server and the latter replies with ok However in this case the server terminates instead of looping again Now both tests pass when run in Concuerror Note that even thes
10. 0 Test for already attached processes and full server module reg_server_tests include_lib eunit include eunit hrl include reg_server hrl already_attached_test gt reg_server start RegNum reg_server attach assertEqual RegNum reg_server attach reg_server stop max_attached_proc_test gt reg_server start L lists seq 1 MAX_ATTACHED Ps spawn_attach lt L assertEqual server_full reg_server attach lists foreach fun Pid gt Pid ok end Ps reg_server stop attach_and_wait Target gt reg_server attach Target done receive ok gt ok end spawn_attach gt Self self Pid spawn fun gt attach_and_wait Self end receive done gt Pid end as the erl files With the above additions the test passes successfully We will work on our next two tasks in one step because they are fairly simple The first is to handle an attach 0 call from an already attached process The server can ei ther ignore the call and return the already allocated regis tration number or alternatively return a special value in dicating an error We will choose the first option here and check it with the first test shown in Test 10 The second task is to handle the case of a process requesting to be come attached when the server is already full of attached processes as determined by MAX_ATTACHED In this case we would like the attach call to return serve
11. Test Driven Development of Concurrent Programs using Concuerror Alkis Gotovos Maria Christakis Konstantinos Sagonas 1 School of Electrical and Computer Engineering National Technical University of Athens Greece 2 Department of Information Technology Uppsala University Sweden alkisg mchrista kostis softlab ntua gr Abstract This paper advocates the test driven development of con current Erlang programs in order to detect early and elim inate the vast majority of concurrency related errors that may occur in their execution To facilitate this task we have developed a tool called Concuerror that exhaustively ex plores process interleaving possibly up to some preemp tion bound and presents detailed interleaving information of any errors that occur We describe in detail the use of Concuerror on a non trivial concurrent Erlang program that we develop step by step in a test driven fashion Categories and Subject Descriptors D 2 4 Software Engineering Software Program Verification D 2 5 Soft ware Engineering Testing and Debugging General Terms Reliability Verification Keywords test driven development Erlang 1 Introduction Erlang is currently gaining popularity mainly due to its built in support for concurrency This support based on asynchronous message passing between processes that in principle do not share any memory not only differs from the concurrency support of most other languages but also
12. al option for executing the test under a simulated distributed semantics without the need for code modifications However in practice enabling this option does not reveal the defect The third way is to activate McErlang s sends_are_sefs option which causes some actions like sends links and monitors to be considered side effects thus enabling a finer grained interleaving semantics This method is by far the most convenient yet it is still experimental according to McErlang s user manual at the time of this writing Returning to the problem of the client calling whereis 1 between the server s reply and exit a possible fix is to have the server unregister itself before replying to a stop request The corrected code that makes all three of our tests pass in Concuerror is shown in Program 7 Program 7 Unregister the server before replying to a stop request loop gt receive REG_REQUEST Target ping gt reply Target pong Loop REG_REQUEST Target stop gt unregister REG_NAME reply Target ok end Next we have to test the case where multiple processes attempt to stop the server concurrently We will test this scenario by spawning two processes making them stop the server and collecting the return values of their stop 0 calls We expect that one call will return ok and the other server_down as shown in Test 5 Running this test in Concuerror results in a large num ber of erroneous inter
13. ast test produces a large number of interleaving sequences more than 800 000 and takes several minutes to complete At this point we can turn on preemption bounding by selecting the Enable preemption bounding option under Edit Preferences and use the default value of two for the preemption bound Running the test again a considerably lower number of interleaving sequences about 1 700 is produced in a matter of seconds However we would also like to know if the previous defect would have been detected if a preemption bound of two were used Temporarily reverting the changes of Program 8 and running the test again we can see that the defect is indeed detected In fact the defect is even detected with a preemption bound of zero This suggests that a low preemption bound may often be enough to reveal many common concurrency errors Our next task is dealing with the case of pinging the server when it is not running The current version of request 1 should readily handle this case without the need for a timeout To check this we employ the tests shown in Test 6 The first test checks that a call to ping 0 returns server_down before starting the server for the first time as well as after starting and stopping the server The second test checks that when a process attempts to ping the server while another process is trying to stop it the ping call will return either pong or server_down Both tests pass successfully and we proceed to our nex
14. de Running analysis Analysis complete checked 4 interleaving s in m0 32s Found 2 erroneous interleaving s Analyze m Stop Figure 3 Concuerror s detailed interleaving information helps understand and fix the error Test Code 5 Test for two concurrent stop calls by two processes Program 8 Monitor the server to deal with multiple con current stop calls multiple_concurrent_stops_test gt Self self reg_server start spawn fun gt Self reg_server stop end spawn fun gt Self reg_server stop end assertEqual lists sort ok server_down lists sort receive_two receive_two gt receive Resultl gt receive Result2 gt Resultl Result2 end end the process sends its request the requesting process will fail with an exception Alternatively if the server exits af ter the request has been sent the requesting process will block waiting for a server reply that will never come We have to provide a way for a process to be informed of whether the server has been stopped by another process after the execution of its whereis 1 call To avoid the ex ceptions instead of the server s registered name we can use its process identifier pid returned by whereis 1 in request 1 Doing this will result in the transformation of the exception errors into deadlocks due to processes block ing on the receive expression of request 1 We avoid requ
15. e program to remove any code duplication Although there exist several testing tools for Erlang the majority of them fails to be effective when used for test driven development in Erlang s concurrent setting EUnit 3 is the Erlang implementation of the popular xUnit testing framework and is reportedly the most used testing tool by Erlang developers 8 Despite its ease of use EUnit executes each test under a single interleaving and is inadequate for detecting concurrency errors 1Concuerror s code its manual and further examples can be found at https github com mariachris Concuerror Quviq s QuickCheck 1 is a property based fuzz testing tool that has been extended with the PULSE scheduler 4 for randomly interleaving processes to detect concurrency errors Besides the random nature of its testing procedure that provides no correctness guarantees the user is re quired to write properties the program should satisfy using a special notation This implies the user s familiarity with the non trivial task of writing properties and additionally excludes the use of existing unit tests McErlang 5 6 is a model checker that utilizes a cus tom runtime simulator of Erlang s concurrency seman tics to explore program state space The ability to deploy monitors containing linear temporal logic formulas makes McErlang very powerful in terms of verification capabil ity Nevertheless McErlang in its default mode of use em pl
16. e modules and then calling eunit test reg_server_tests EUnit reports that all three tests pass We can try it again and again the result is the same The reason is that the er rors displayed in Concuerror are caused by interleaving sequences that are very unlikely to happen in practice The interleaving scenarios that are responsible for these errors are almost impossible to reveal with traditional test ing tools like EUnit yet it is still possible that they actu ally occur Back to Concuerror and in the Process interleaving panel we can see that both errors have the same cause Between the server s reply and its actual exit the client process manages to call whereis 1 it even manages to send its second stop request in one of the two interleaving sequences Because the server has not exited yet the call to whereis 1 does not return undefined Subsequently the server exits and as a result the client either fails with an exception in case it tries to send a stop request to a process that is not registered anymore or blocks in case it has already sent the request and is waiting for an an swer from the non existing server The detailed sequence for the second case as viewed in the Concuerror GUI is shown in Figure 3 Before fixing the problem let us run our last test in McErlang using its default configuration Like EUnit McErlang reports no errors The reason is that McErlang in its default mode of use only preempts process
17. e server Advanced issues Let us now handle the case of multiple stop calls We will first test the case of two consecutive stop calls by one pro cess and then that of two concurrent stop calls by two pro cesses As shown in Test 4 when a process calls stop 0 and the server is not running the return value should be server_down Running this test in Concuerror results in three erroneous interleaving sequences two due to an ex ception and one due to a deadlock Looking at the Process interleaving panel we notice that the first exception hap pens when the client process attempts to send a message to the already exited server process using its registered name To fix this error we can use the whereis 1 built in to check whether the server name is registered that is whether the server is running before sending the stop Program 5 Use whereis 1 before sending a message to the server request Request gt case whereis REG_NAME of undefined gt server_down Pid gt REG_NAME REG_REQUEST self Request receive REG_REPLY Reply gt Reply end end message In fact we can do this inside request 1 so that the check is performed before any message is sent to the server as shown in Program 5 Running the test again we see that the first error is fixed but the other two are still there Now is a good point to try running the tests using EUnit rather than Con cuerror This can be done by first compiling th
18. e small tests produce more than one interleaving sequence three in this case due to the different exit orders of the two testing processes Before we continue let us refactor the code of Program 3 to remove some of the duplication that was introduced during our last step In Program 4 we define functions request 1 and reply 2 to handle the sending and receiving of messages between client and server The tests still pass after the refactoring start_stop_test gt assertEqual ok reg_server start assertEqual ok reg_server stop ping_test gt reg_server start assertEqual pong reg_server ping assertEqual pong reg_server ping reg_server stop Program 4 The refactored code of Program 3 stop gt request stop ping gt request ping loop gt receive REG_REQUEST Target ping gt reply Target pong Loop REG_REQUEST Target stop gt reply Target ok end request Request gt REG_NAME REG_REQUEST self Request receive REG_REPLY Reply gt Reply end reply Target Reply gt Target REG_REPLY Reply Test Code 4 Test for two stop calls by one process multiple_stops_test gt reg_server start assertEqual ok reg_server stop assertEqual server_down reg_server stop so at this point we are able to perform the basic operations of starting pinging and stopping our server 4 3 Starting and stopping th
19. ease in the number of interleaving sequences with respect to the number of processes This suggests writing our tests to use only a few processes and then generalizing their results for an arbitrary number of them Last but not least besides revealing errors Concuerror also helped us understand their cause by displaying de tailed interleaving information This is better experienced by actually running Concuerror through the example of this paper By walking through the erroneous interleaving sequences we could quickly understand and correct the source of each defect The complete code of our example can be found at https github com mariachris Concuerror under the resources tdd directory References 1 T Arts J Hughes J Johansson and U Wiger Testing telecoms software with Quviq QuickCheck In Proceedings of the 2006 ACM SIGPLAN Workshop on Erlang pages 2 10 New York NY USA 2006 ACM 2 K Beck Test Driven Development By Example Addison Wesley Longman Publishing Co Inc Boston MA USA 2002 3 R Carlsson and M R mond EUnit A lightweight unit testing framework for Erlang In Proceedings of the 2006 ACM SIG PLAN Workshop on Erlang pages 1 1 New York NY USA 2006 ACM K Claessen M Pa ka N Smallbone J Hughes H Svensson T Arts and U Wiger Finding race conditions in Erlang with QuickCheck and PULSE In Proceedings of the 14th ACM SIG PLAN International Conference on Functional Program
20. emption bounding so we have successfully completed the implementation of the functions for starting and stopping our server 4 4 Attaching processes Any process should be able to become attached to our server A unique integer that for our purposes will be called a registration number is assigned to each attached process The server only allows for a limited number of attached processes We will define the maximum number Program 10 Use try catch to avoid spurious server processes start gt case whereis REG_NAME of undefined gt Pid spawn fun gt loop end try register REG_NAME Pid of true gt ok catch error badarg gt Pid REG_REQUEST kill already_started end _Pid gt already started end loop gt receive REG_REQUEST Target ping gt reply Target pong Loop REG_REQUEST Target stop gt unregister REG_NAME reply Target ok REG_REQUEST kill gt killed end Test Code 9 Test for attaching two processes to the server attach_test gt Self self reg_server start RegNum1 reg_server attach spawn fun gt RegNum2 reg_server attach assertEqual RegNum2 reg_server ping assertEqual false RegNuml RegNum2 Self done end assertEqual RegNum1 reg_server ping receive done gt reg_server stop end of attached processes in the MAX_ATTACHED macro of an external reg_server hrl file so that it can
21. es at receive expressions although we have just seen that ad ditional preemption points are needed to reveal the partic ular defect There are three ways to detect the problem in McErlang The first is to manually insert preemption points us ing the mce_erl pause 1 call provided by the tool In Program 6 we have used Concuerror s details about the problem to insert just enough preemption points for McEr lang to also detect it Manually inserting preemption points is clearly a tedious task even when their locations are priorly known which is typically not the case when ignorant about the possibility of concurrency errors at particular program points Moreover the need for alter ations in the original program makes the tool less usable and code maintenance more difficult Program 6 Manual insertion of preemption points to de tect the problem in McErlang request Request gt Whereis whereis REG_NAME mce_er1 pause fun gt case Whereis of undefined gt server_down _Pid gt REG_NAME REG_REQUEST self Request receive REG_REPLY Reply gt Reply end end end reply Target Reply gt Target REG_REPLY Reply mce_erl pause fun gt ok end The second way also involves modifying the program so that every process is spawned on a separate node This approach not only alters the existing code but also changes its intended semantics In theory McErlang also provides an experiment
22. est Request gt case whereis REG_NAME of undefined gt server_down Pid gt Ref monitor process Pid Pid REG_REQUEST self Request receive REG_REPLY Reply gt demonitor Ref flush Reply DOWN Ref process Pid Reason gt server_down end end these deadlocks by monitoring the server process through a monitor 2 call just before the request message is sent If the server has already exited or exits after the monitor ing call the client process will receive a DOWN message from the Erlang runtime and can return server_down Oth erwise the process will receive a normal reply from the server In any case a message will be received and there fore the process will never block The changes made in the server code are shown in Program 8 A call to demonitor 2 with the flush option is used to stop monitoring the server and discard the DOWN message in case the server has al ready exited Test Code 6 Test calling ping 0 when the server is not running ping_failure_test gt assertEqual server_down reg_server ping reg_server start reg_server stop assertEqual server_down reg_server ping ping_concurrent_failure_test gt reg_server start spawn fun gt R reg_server ping Results pong server_down assertEqual true Lists member R Results end reg_server stop After making the above changes all tests pass Note that our l
23. first test uses assertEqual to check that start 0 returns ok Note that functions with a _test suffix in their name are auto exported by EUnit thus no export attribute is needed The first version of the server module is shown in Program 1 The module exports the start 0 function that just returns ok Program 1 The initial registration server module module reg_server export start 0 start gt ok It is time to run our test using Concuerror The Con cuerror GUI is composed of several panels see Figure 1 The Modules panel on the upper left side displays a list of Concuerror File Edit Module Run View Help Modules sikis Desktop tdd reg_server erl Process interleaving bikis Desktop tddireg_server_tests erl Log Problems validating file home alkis Desktop tdd reg server tests erl Instrumenting file home alkis Desktop tdd reg_server tests erl Compiling instrumented code Validating file home alkis Desktop tdd reg server erl Instrumenting file home alkis Desktop tdd reg_server erl Compiling instrumented code Running analysis analysis complete checked 1 interleaving s in m0 00s Analyze No errors found Main Source Errors Process interleaving Assertion violation Process P1 exits Assertion violation reg_server_tests erl 6 Log Problems Validating file home alkis Desktop tdd reg_server_tests erl Instrumenting file home alkis Desktop tdd reg_
24. leaving sequences Looking at the first of them we notice that both processes call whereis 1 before the server stops The problem is similar to the one we had in our previous step If the server has exited before Concuerror File Edit Module Run View Help Modules Main A esktop tdd reg_server erl i Errors Psktop tdd reg_server_tests erl Deadlock P1 Exception badarg Process interleaving Process P1 spawns process P1 1 Process P1 registers process P1 1 as reg_server Process P1 requests the pid of process reg_server P1 1 Process P1 sends message reg_request lt 0 327 0 gt stop to process P1 1 Process P1 1 receives message reg_request lt 0 327 0 gt stop from process P1 Process P1 1 sends message reg_reply ok to process P1 Process P1 receives message reg_reply ok from process P1 1 Process P1 requests the pid of process reg_server P1 1 Functions Process P1 sends message reg_request lt 0 327 0 gt stop to process P1 1 multiple_stops_test O ping_test O start_stop _test O Process P1 1 exits normal Process P1 blocks Log problems Validating file home alkis Desktop tdd reg_server_tests erl Instrumenting file home alkis Desktop tdd reg server tests erl Compiling instrumented code Validating file home alkis Desktop tdd reg server erl Instrumenting file home alkis Desktop tdd reg server erl Compiling instrumented co
25. m Reg reply Target RegNum NewFree ordsets from_list NewFreeList NewState State state free NewFree reg NewReg Loop NewState end end end Test Code 11 Test for detaching detach_test gt reg_server start reg_server attach reg_server detach assertEqual pong reg_server ping reg_server stop Test Code 12 Test for reattaching after detaching detach_attach_test gt Self self reg_server start L lists seq 1 MAX_ATTACHED 1 Ps spawn_attach lt L LastProc spawn fun gt RegNum reg_server attach reg_server detach Self RegNum receive ok gt ok end end receive RegNum gt ok end assertEqual RegNum reg_server attach lists foreach fun Pid gt Pid ok end LastProc Ps reg_server stop 4 5 Detaching processes We have finished our tasks concerning the attachment of processes and now proceed to handling their detachment from the server When a process is detached from the server using a detach 0 call it should no longer have an assigned registration number thus a ping call to the server after the process detachment should return pong This is checked by the test in Test 11 Moreover the server should make the corresponding registration number avail able to future processes requesting attachment To check Program 13 Add detach 0 to the server module reg_server export attach detach 0
26. ming pages 149 160 New York NY USA 2009 ACM 5 C B Earle and L Fredlund Recent improvements to the McErlang model checker In Proceedings of the 8th ACM SIGPLAN Workshop on Erlang pages 93 100 New York NY USA 2009 ACM L A Fredlund and H Svensson McErlang A model checker for a distributed functional programming language In Pro ceedings of the 12th ACM SIGPLAN International Conference on Functional Programming pages 125 136 New York NY USA 2007 ACM 7 M Musuvathi and S Qadeer Iterative context bounding for systematic testing of multithreaded programs In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Lan guage Design and Implementation pages 446 455 New York NY USA 2007 ACM T Nagy and A Nagyn Vig Erlang testing and tools survey In Proceedings of the 7th ACM SIGPLAN Workshop on Erlang pages 21 28 New York NY USA 2008 ACM 4 paan 6 a 8 pan
27. ocess is detached only when it calls detach 0 If an attached process exits without hav ing been detached on its own its registration number will remain occupied forever Consequently our last task is to enforce detaching a process as soon as it exits To check this we modify the test in Test 11 so that the last process being spawned instead of explicitly detaching itself sim ply terminates its execution The main testing process tries to attach itself after receiving the EXIT message from this previously attached process For the EXIT message to be received a process_flag 2 call is used to activate the trap_exit flag of the main process The test is shown in Test 14 Program 14 Deal with trying to detach an unattached process loop state free Free reg Reg State gt receive REG_REQUEST Target detach gt case dict is_key Target Reg of false gt reply Target ok loop State true gt RegNum dict fetch Target Reg Loop NewState end end Test Code 14 Test for detaching a process as soon as it exits detach_on_exit_test gt Self self reg_server start L lists seq 1 MAX_ATTACHED 1 Ps spawn_attach lt L process_flag trap_exit true LastProc spawn_link fun gt Self reg_server attach end receive RegNum gt ok end receive EXIT LastProc normal gt ok end assertEqual RegNum reg_server attach lists foreach
28. oys a very coarse grained process interleaving seman tics The detection of subtle concurrency errors similar to those found in Section 4 might require the manual inser tion of unobvious code a task that is tedious alters the original test and does not concord with the philosophy of test driven development 3 A Glimpse of Concuerror As mentioned Concuerror detects concurrency errors that may occur when an Erlang function usually a test is ex ecuted Existing tests can be readily used in Concuerror without requiring any modifications of the program un der test By systematically interleaving the participating processes Concuerror effectively explores the program s state space and detects interleaving sequences with unin tended effects namely abnormal process exits due to an exception assertion violations and deadlocks In Concuer ror any program state where one or more processes are blocked on a receive statement and no other process is available for scheduling is considered a deadlock Under the hood Concuerror uses a stateless searching approach to produce interleaving sequences Preemption points i e points in the program where a context switch is allowed to happen are only placed at side effecting opera tions like sends receives process exits etc Interleaving redundancy is further reduced by avoiding sequences that involve process blocks on receive statements To make the tool even faster the user can opt for a
29. r_full as shown in the second test of Test 10 For the tests to pass before attaching the requesting process we need to check whether it already has a reg istration number and if not whether there are any free registration numbers This is easily done inside the server loop as shown in Program 12 Our new tests pass successfully in Concuerror The second test produces 822 interleaving sequences for a preemption bound of two The current execution of our test contains a total of four processes the initial process the server process and two additional spawned processes Let us change the value of MAX_ATTACHED to one so that our test contains three processes Leaving the preemp tion bound at two there are now only 65 interleaving se quences produced Trying the same with MAX_ATTACHED equal to three and four 9 789 and 118 038 interleaving se quences are produced respectively This clearly indicates that the number of interleaving sequences grows exponen tially as the number of testing processes increases Program 12 Extend server to deal with already registered processes and full server loop state free Free reg Reg State gt receive REG_REQUEST Target attach gt case dict find Target Reg of ok RegNum gt reply Target RegNum Loop State error gt case ordsets to_list Free of gt reply Target server_full loop State RegNum NewFreeList gt NewReg dict store Target RegNu
30. ree Free reg Reg State gt receive REG_REQUEST Target attach gt RegNum NewFreeList ordsets to_list Free NewReg dict store Target RegNum Reg reply Target RegNum NewFree ordsets from_list NewFreeList NewState State state free NewFree reg NewReg Loop NewState REG_REQUEST Target ping gt case dict find Target Reg of ok RegNum gt reply Target RegNum error gt reply Target pong end loop State end use a dictionary to store mappings from registered pro cesses pids to their corresponding registration numbers Both structures can be packed into a record that will rep resent the state of the server and will be passed as an ar gument to its loop Other than that the request reply in frastructure that we have created so far can also be used here in order to automatically handle the case of calling attach when the server is down The implementation of all of the above is shown in Program 11 Every time a process requests to become attached the server removes a free registration number from its set and adds a pid to registration number mapping to the dictio nary Note that the header file reg_server hrl contains only the attribute define MAX_ATTACHED 2 A small number is used here to simplify our testing We do not need to import this header file in Concuerror it is auto matically recognized since it resides in the same directory Test Code 1
31. rors namely process crashes assertion violations and deadlocks that might occur during the execution of these tests The temptation to describe in detail the techniques used by Concuerror is very strong but we will try to resist it a forthcoming companion paper will deal with this subject Instead the purpose of the current paper is to advocate test driven development of concurrent Erlang programs using small step iterations and unit tests while describing in detail how Concuerror can be used in practice as a testing and debugging aid For this purpose we will write and test in a loosely test driven fashion a simple example program that is a typical use case of concurrent Erlang We warn our readers that some of the concurrency errors that Concuerror will detect may surprise even seasoned Erlang programmers The next section briefly overviews the suitability or lack thereof of existing tools for test driven development in Erlang Section 3 overviews Concuerror s functionality and characteristics followed by Section 4 that presents in detail the test driven development of an example program with the iterative use of Concuerror The paper ends with some concluding remarks 2 Test Driven Development in Erlang Test driven development 2 is a software development practice that suggests using a workflow of small three step iterations each of them consisting in writing a small failing test quickly making it work and refactoring th
32. server_tests erl Compiling instrumented code Validating file home alkis Desktop tdd reg_server erl Instrumenting file home alkis Desktop tdd reg_server erl Compiling instrumented code Running analysis Analysis complete checked 1 interleaving s in 0m0 01s Found 1 erroneous interleaving s Figure 1 Running a test that passes in Concuerror s GUI all Erlang modules imported to Concuerror These modules will be instrumented when Concuerror begins its analysis The Functions panel on the lower left side displays a list of all exported functions defined in the module selected from the Modules panel The Log panel on the lower right side displays information about Concuerror actions Addition ally by selecting the Source tab next to Main we can see the source code of the selected module Let us run our test before explaining the rest of the GUI functionality To import our modules we either click the Add button or select File Add Through the browse dialog we locate our two modules in the file system se lect them and click Open Our modules have now been imported and added to the Modules panel By selecting module reg_server_tests from this panel testing func tion start_test 0 appears in the Functions panel For the time being we will disable preemption bounding by unchecking the Enable preemption bounding option under Edit gt Preferences We can now select the test function and click Analyze to e
33. t task namely dealing with multiple calls to start 0 Like we did with multiple stop calls we will test mul tiple start calls by first using one process and then two A call to start 0 should return already_started in case the server is already running The corresponding single process test is shown in Test 7 To make this test work we call whereis 1 in start 0 before starting the server If whereis 1 returns undefined the server is spawned and registered as before otherwise the server is already run ning so already_started is returned The newly added server code is shown in Program 9 The test passes with the new version of start 0 and we are ready to write the two process variant The test for two concurrent start 0 calls is shown in Test 8 and is similar to the one we used in Test 5 to test for two concurrent stop 0 calls Two processes are spawned and concurrently attempt to start the server One of them Test Code 7 Test for two start calls by one process multiple_starts_test gt reg_server start assertEqual already_started reg_server start reg_server stop Program 9 Check if the server is already running before starting it start gt case whereis REG_NAME of undefined gt Pid spawn fun gt loop end register REG_NAME Pid ok _Pid gt already_started end Test Code 8 Test for two concurrent start calls by two processes multiple_concurrent_starts_test gt Self
34. ual pong reg_server ping assertEqual pong reg_server ping registered as expected we will create an auxiliary ping 0 function that returns pong if the server responds In case the server is down the ping function should probably timeout after a while but we leave this task for later We also leave for later the case of start 0 being called more than once by either one or more processes At this point we want to spawn the server process register it and make it respond to a ping call To this end we create ping_test 0 shown in Test 2 We call ping 0 twice to make sure that the server loop is correct To make the test pass we spawn a new process to start the server register it under the name reg_server and make it execute function loop 0 as shown in Program 2 Inside its loop the server receives ping requests and replies with pong messages Function ping 0 sends a ping request to the server and waits for a pong response The macros REG_REQUEST and REG_REPLY are used to avoid con fusion with messages sent by other processes Running our tests in Concuerror results in both of them reporting a deadlock We should be expecting this because the server runs in a loop and is blocked waiting for a re quest even after the client process i e the process run ning the test function has exited Note that Concuerror reports a deadlock because the only process alive is blocked on a receive statement To avoid the aforemen
35. xecute the test under Concuerror The Log panel informs us about the successful instrumentation and compilation of our modules as well as about the com plete execution of one interleaving sequence without any errors see Figure 1 Let us now change the return value of start 0 from ok to error and run the analysis again This time an error ap pears in the Errors panel namely an assertion violation on line 6 of our testing module Furthermore in the Process interleaving panel we can see the erroneous interleaving sequence It consists solely of our testing process abnor mal exit see Figure 2 We can also select the Problems tab next to Log to switch to the panel that displays additional information about the specific error The expected value was ok but the call to start returned error We change the return value back to ok before proceeding These are the basics about importing modules and run ning tests using the Concuerror GUI In the next section we begin implementing the server s functionality 4 2 Starting and stopping the server The basics We will create a server process and register it under the name reg_server To test that the server is spawned and Figure 2 Information about an erroneous interleaving Test Code 2 Add a ping test module reg_server_tests include_lib eunit include eunit hrl start_test gt assertEqual ok reg_server start ping_test gt reg_server start assertEq
Download Pdf Manuals
Related Search