K.C. Wang Systems Programming in Unix/Linux Systems Programming in Unix/Linux K. C. Wang Systems Programming in Unix/Linux K.C.Wang SchoolofElectricalEngineering WashingtonStateUniversity Pullman,WA,USA ISBN978-3-319-92428-1 ISBN978-3-319-92429-8 (eBook) https://doi.org/10.1007/978-3-319-92429-8 LibraryofCongressControlNumber:2018945425 #SpringerInternationalPublishingAG,partofSpringerNature2018 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeor part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway, andtransmissionorinformationstorageandretrieval,electronicadaptation,computersoftware,or bysimilarordissimilarmethodologynowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthis publication does not imply, even in the absence of a specific statement, that such names are exemptfromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthors,andtheeditorsaresafetoassumethattheadviceandinformationin thisbookarebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remainsneutralwithregardtojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Dedicated to Cindy Preface Systems programming is an indispensable part of Computer Science and ComputerEngineeringeducation.SystemprogrammingcoursesinComputer Science/Engineering curriculums play two important roles. First, it provides studentswithawiderangeofknowledgeaboutcomputersystemsoftwareand advanced programming skills, allowing them to interface with operating system kernel, perform file operations and network programming, and make efficientuseofsystemresourcestodevelopapplicationprograms.Second,it prepares students with needed background to pursue advanced studies in Computer Science/Engineering, such as operating systems, embedded systems, database systems, data mining, artificial intelligence, computer networks, and distributed and parallel computing. Due to its importance, systems programming in Unix/Linux has been a popular subject matter in CS/CE education and also for self-study by advanced programmers. As a result,thereareatremendousnumberofbooksandonlinearticlesinthisarea. Despitethese,IstillfinditdifficulttochooseasuitablebookfortheSystems Programming course I teach at WSU. For many years, I had to use my own class notes and programming assignmentsin the course.Aftercareful think- ing,Ihavedecidedtoputtogetherthematerialsintoabookform. Thepurposeofthisbookistoprovideasuitableplatformforteachingand learningthetheoryandpracticeofsystemsprogramming.Unlikemostother books, this book covers systems programming topics in greater depth and it stresses programming practice. It uses aseries of programmingprojects to let students apply their acquired knowledge and programming skills to develop practical and useful programs. The book is intended as a textbook in technical-oriented systems programming courses. It contains detailed example programs with complete source code, making it suitable for self- studyalso. Undertaking this book project has proved to be another very demanding andtime-consumingendeavor.Whilepreparingthemanuscriptsforpublica- tion,Ihavebeenblessedwiththeencouragementandhelpfrommanypeople. Iwouldliketotakethisopportunitytothankallofthem.Iwanttoespecially thank Yan Zhang for his help in preparing figures for the book and proof- readingthemanuscript. vii viii Preface Special thanks go to Cindy for her continuing support and inspirations, which have made this book possible. Above all, I would like to thank my familyforbearingwithmewithendlessexcusesofbeingbusyallthetime. Sample solutions of programming projects in the book are available for downloadathttp://wang.eecs.wsu.edu/~kcw.Forsourcecode,pleasecontact theauthorbyemail. Pullman,WA,USA K.C.Wang April,2018 Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 AboutThisBook. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 RolesofSystemsProgramming. . . . . . .. . . . . . . . .. . . 1 1.3 ObjectivesofThisBook. . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 StrengthenStudentsProgramming Background. . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 ApplicationsofDynamicDataStructures. . . . 2 1.3.3 ProcessConceptandProcess Management. . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.4 ConcurrentProgramming. . . . . . . . . . . . . . . . 3 1.3.5 TimerandTimeFunctions. . . . . . . . . . . . . . . 3 1.3.6 Signals,SignalProcessingandIPC. . . . . . . . . 3 1.3.7 Filesystem. . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.8 TCP/IPandNetworkProgramming. . . . . . . . . 4 1.4 IntendedAudience. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 UniqueFeaturesofThisBook. . . . . . . . . . . . . . . . . . . 4 1.6 UseThisBookAsTextbookinSystems ProgrammingCourses. . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 OtherReferenceBooks. . . . . . . . . . . . . . . . . .. . . . . . . 7 1.8 IntroductiontoUnix. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.8.1 AT&TUnix. . . . . . . . . . . . . . . . . . . . . . . . . 7 1.8.2 BerkeleyUnix. . . . . . . . . . . . . . . . . . . . . . . . 8 1.8.3 HPUnix. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8.4 IBMUnix. . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8.5 SunUnix. . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.9 IntroductiontoLinux. . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.10 LinuxVersions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.10.1 DebianLinux. . . . . . . . . . . . . . . . . . . . . . . . 9 1.10.2 UbuntuLinux. . . . . . . . . . . . . . . . . . . . . . . . 9 1.10.3 LinuxMint. . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.10.4 RPM-BasedLinux. . . . . . . . . . . . . . . . . . . . . 10 1.10.5 SlackwareLinux. . . . . . . . . . . . . . . . . . . . . . 10 1.11 LinuxHardwarePlatforms. . . . . . . . . . . . . . . . . . . . . . 10 ix x Contents 1.12 LinuxonVirtualMachines. . . . . . . . . . . . . . . . . . . . . . 10 1.12.1 VirtualBox. . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.12.2 VMware. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.12.3 DualBootSlackwareandUbuntuLinux. . . . . 14 1.13 UseLinux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.13.1 Linuxkernelimage. . . . . . . . . . . . . . . . . . . . 15 1.13.2 LinuxBooters. . . . . . . . . . . . . . . . . . . . . . . . 15 1.13.3 LinuxBooting. . . . . . . . . . . . . . . . . . . . . . . . 15 1.13.4 LinuxRun-levels. . . . . . . . . . . . . . . . . . . . . . 16 1.13.5 LoginProcess. . . . . . . . . . . . . . . . . . . . . . . . 16 1.13.6 CommandExecutions. . . . . . . . . . . . . . . . . . 16 1.14 UseUbuntuLinux. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.14.1 UbuntuVersions. . . . . . . . . . . . . . . . . . . . . . 16 1.14.2 SpecialFeaturesofUbuntuLinux. . . . . . . . . . 17 1.15 Unix/LinuxFileSystemOrganization. . . . . . . . . . . . . . 18 1.15.1 FileTypes. . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.15.2 FilePathnames. . . . . . . . . . . . . . . . . . . . . . . 19 1.15.3 Unix/LinuxCommands. . . . . . . . . . . . . . . . . 19 1.15.4 LinuxManPages. . . . . . . . . . . . . . . . . . . . . 19 1.16 UbuntuLinuxSystemAdministration. . . . . . . . . . . . . . 20 1.16.1 UserAccounts. . . . . . . . . . . . . . . . . . . . . . . . 20 1.16.2 AddNewUser. . . . . . . . . . . . . . . . . . . . . . . 20 1.16.3 ThesudoCommand. . . .. . . . .. . . .. . . . .. . 21 1.17 Summary. . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . 21 References. . . . .. . . . .. . . .. . . . .. . . . .. . . . .. . . .. . . . .. . 21 2 ProgrammingBackground. . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1 TextEditorsinLinux. . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.1 Vim. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.2 Gedit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.3 Emacs. . . .. . . .. . . . .. . . . .. . . . .. . . . .. . 24 2.2 UseTextEditors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1 UseEmacs. . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 EmacsMenus. . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.3 IDEofEmacs. . . . . . . . . . . . . . . . . . . . . . . . 26 2.3 ProgramDevelopment. . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.1 ProgramDevelopmentSteps. . . . . . . . . . . . . 27 2.3.2 VariablesinC. . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.3 Compile-LinkinGCC. . . . . . . . . . . . . . . . . . 28 2.3.4 Staticvs.DynamicLinking. . . . . . . . . . . . . . 29 2.3.5 ExecutableFileFormat. . . . . . . . . . . . . . . . . 30 2.3.6 Contentsofa.outFile. .. . . . .. . . . .. . . . .. . 30 2.3.7 ProgramExecution. . . . . . . . . . . . . . . . . . . . 31 2.3.8 ProgramTermination. . . . . . . . . . . . . . . . . . . 32 2.4 FunctionCallinC. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.1 Run-TimeStackUsagein32-BitGCC. . . . . . 33 2.4.2 StackFrames. . .. . . . .. . . . .. . . . .. . . . .. . 35 2.4.3 ReturnFromFunctionCall. . . . . . . . . . . . . . . 35 Contents xi 2.4.4 LongJump. . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.5 Run-TimeStackUsagein64-BitGCC. . . . . . 37 2.5 LinkCProgramwithAssemblyCode. . . . . . . . . . . . . . 40 2.5.1 ProgramminginAssembly. . . . . . . . . . . . . . . 41 2.5.2 ImplementFunctionsinAssembly. . . . . . . . . 43 2.5.3 CallCfunctionsfromAssembly. . . . . . . . . . . 44 2.6 LinkLibrary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6.1 StaticLinkLibrary. . . . . . . . . . . . . . . . . . . . 45 2.6.2 DynamicLinkLibrary. . . . . . . . . . . . . . . . . . 46 2.7 Makefile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.7.1 MakefileFormat. . . . . . . . . . . . . . . . . . . . . . 46 2.7.2 ThemakeProgram. . . . . . . . . . . . . . . . . . . . 46 2.7.3 MakefileExamples. . . . . . . . . . . . . . . . . . . . 47 2.8 TheGDBDebugger. . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.8.1 UseGDBinEmacsIDE. . . . . . . . . . . . . . . . 53 2.8.2 AdvicesonUsingDebuggingTools. . . . . . . . 58 2.8.3 CommonErrorsinCprograms. . . . . . . . . . . . 58 2.9 StructuresinC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.9.1 StructureandPointers. . . . . . . . . . . . . . . . . . 64 2.9.2 TypecastinC. . . . . . . . . . . . . . . . . . . . . . . . 64 2.10 LinkListProcessing. . . . . . . . . . . . . . . . . .. . . . . . . . . 66 2.10.1 LinkLists. . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.10.2 LinkListOperations. . . . . . . . . . . . . . . . . . . 66 2.10.3 BuildLinkList. . . . . . . . . . . . . . . . . . . . . . . 67 2.10.4 LinkListTraversal. . . . . . . . . . . . . . . . . . . . 70 2.10.5 SearchLinkList. . . . . . . . . . . . . . . . . . . . . . 72 2.10.6 InsertOperation. . .. . . . . .. . . . . .. . . . . .. . 72 2.10.7 PriorityQueue. . . . . . . . . . . . . . . . . . . . . . . . 73 2.10.8 DeleteOperation. . . . . . . . . . . . . . . . . . . . . . 74 2.10.9 CircularLinkList. . . . . . . . . . . . . . . . . . . . . 75 2.10.10 Open-EndedCStructures. . . . . . . . . . . . . . . . 75 2.10.11 DoublyLinkLists. . . . . . . . . . . . . . . . . . . . . 76 2.10.12 DoublyLinkListsExamplePrograms. . . . . . . 76 2.11 Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.12 BinaryTree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.12.1 BinarySearchTree. . . . . . . . . . . . . . . . . . . . 85 2.12.2 BuildaBinarySearchTree(BST). . . . . . . . . 86 2.12.3 BinaryTreeTraversalAlgorithms. . . . . . . . . . 87 2.12.4 Depth-FirstTraversalAlgorithms. . . . . . . . . . 87 2.12.5 Breadth-FirstTraversalAlgorithms. . . . . . . . . 88 2.13 ProgrammingProject:Unix/LinuxFileSystem TreeSimulator. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 2.13.1 Unix/LinuxFileSystemTree. . . . . . . . . . . . . 90 2.13.2 ImplementGeneralTreebyBinaryTree. . . . . 90 2.13.3 ProjectSpecificationandRequirements. . . . . . 90 2.13.4 CommandsSpecification. . . . . . . . . . . . . . . . 91 2.13.5 ProgramOrganization. . . . . . . . . . . . . . . . . . 91