{"id":5633,"date":"2013-01-07T07:00:00","date_gmt":"2013-01-07T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2013\/01\/07\/understanding-the-classical-model-for-linking-groundwork-the-algorithm\/"},"modified":"2013-01-07T07:00:00","modified_gmt":"2013-01-07T07:00:00","slug":"understanding-the-classical-model-for-linking-groundwork-the-algorithm","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20130107-00\/?p=5633","title":{"rendered":"Understanding the classical model for linking, groundwork: The algorithm"},"content":{"rendered":"<p><P>\nThe classical model for linking goes like this:\n<\/P>\n<P>\nEach OBJ file contains two lists of symbols.\n<\/P>\n<OL>\n<LI>Provided symbols:\n    These are symbols the OBJ contains definitions for.\n<LI>Needed symbols:\n    These are symbols the OBJ would like the definitions for.\n<\/OL>\n<P>\n(The official terms for these are <I>exported<\/I> and\n<I>imported<\/I>,\nbut I will use\n<I>provided<\/I> and <I>needed<\/I> to avoid confusion with\nthe concepts of exported and imported functions in DLLs,\nand because <I>provided<\/I> and <I>needed<\/I> more clearly\ncaptures what the two lists are for.)\n<\/p>\n<p><P>\nNaturally, there is other bookkeeping information in there.\nFor example, for provided symbols, not only is the name given,\nbut also additional information on locating the definition.\nSimilarly, for needed symbols, in addition to the name,\nthere is also information about what should be done once its\ndefinition has been located.\n<\/P>\n<P>\nCollectively, provided and needed symbols are known as\n<I>symbols with external linkage<\/I>,\nor just <I>externals<\/I> for short.\n(Of course, by giving them the name\n<I>symbols with external linkage<\/I>,\nyou would expect there to be things known as\n<I>symbols with internal linkage<\/I>,\nand you&#8217;d be right.)\n<\/P>\n<P>\nFor example, consider this file:\n<\/P>\n<PRE>\n\/\/ inventory.c<\/p>\n<p>extern int InStock(int id);<\/p>\n<p>int GetNextInStock()\n{\n  static int Current = 0;\n  while (!InStock(++Current)) { }\n  return Current;\n}\n<\/PRE>\n<P>\nThis very simple OBJ file has one provided symbol,\n<CODE>Get&shy;Next&shy;In&shy;Stock<\/CODE>:\nThat is the object defined in this file that can be used by other files.\nIt also has one needed symbol,\n<CODE>In&shy;Stock<\/CODE>:\nThat is the object required by this file in order to work,\nbut which the file itself did not provide a definition for.\nIt&#8217;s hoping that somebody else will define it.\nThere&#8217;s also a symbol with internal linkage:\n<I>Current<\/I>,\nbut that&#8217;s not important to the discussion,\nso I will ignore it from now on.\n<\/P>\n<P>\nOBJ files can hang around on their own,\nor they can be bundled together into a LIB file.\n<\/P>\n<P>\nWhen you ask the linker to generate a module,\nyou hand it a list of OBJ files and a list of LIB files.\nThe linker&#8217;s goal is to <I>resolve<\/I> all of the\n<I>needed symbols<\/I>\nby matching them up to a <I>provided symbol<\/I>.\nEventually, everything needed will be provided,\nand you have yourself a module.\n<\/P>\n<P>\nTo do this, the linker keeps track of which symbols in the module\nare resolved and which are unresolved.\n<\/P>\n<UL>\n<LI>A resolved symbol is one for which a provided symbol has been\n    located and added to the module.\n    Under the classical model, a symbol can be resolved only once.\n    (Otherwise, the linker wouldn&#8217;t know which one to use!)\n<LI>An unresolved symbol is one that is needed by the module,\n    but for which no provider has yet been identified.\n<\/UL>\n<P>\nWhenever the linker adds an OBJ file to the module,\nit goes through the list of provided and needed symbols\nand updates the list of symbols in the module.\nThe algorithm for updating this list of symbols is obvious\nif you&#8217;ve been paying attention, because it is a simple matter\nof preserving the invariants described above.\n<\/P>\n<P>\nFor each <I>provided<\/I> symbol in an OBJ file added to a module:\n<\/P>\n<UL>\n<LI>If the symbol is already in the module marked as <I>resolved<\/I>,\n    then\n    <A HREF=\"http:\/\/msdn.microsoft.com\/library\/72zdcz6f.aspx\">\n    raise an error<\/A>\n    complaining that an object has multiple\n    definitions.\n<LI>If the symbol is already in the module\n    marked as <I>unresolved<\/I>, then change its marking to <I>resolved<\/I>.\n<LI>Otherwise, the symbol is not already in the module.\n    Add it and mark it as <I>resolved<\/I>.\n<\/UL>\n<P>\nFor each <I>needed<\/I> symbol in an OBJ file added to a module:\n<\/P>\n<UL>\n<LI>If the symbol is already in the module marked as <I>resolved<\/I>,\n    then leave it marked as <I>resolved<\/I>.\n<LI>If the symbol is already in the module marked as <I>unresolved<\/I>,\n    then leave it marked as <I>unresolved<\/I>.\n<LI>Otherwise, the symbol is not already in the module.\n    Add it and mark it as <I>unresolved<\/I>.\n<\/UL>\n<P>\nThe algorithm the linker uses to resolve symbols goes like this:\n<UL>\n<LI>Initial conditions:\n    Add all the explicitly-provided OBJ files to the module.\n<LI>While there is an unresolved symbol:\n    <UL>\n    <LI>Look through all the LIBs\n        for the first OBJ to provide the symbol.\n    <LI>If found: Add that OBJ to the module.\n    <LI>If not found:\n        <A HREF=\"http:\/\/msdn.microsoft.com\/en-us\/library\/f6xx1b1z.aspx\">\n        Raise an error<\/A> complaining of an unresolved external.\n        (If the linker has the information available,\n        it may provide\n        <A HREF=\"http:\/\/msdn.microsoft.com\/en-us\/library\/799kze2z.aspx\">\n        additional details<\/A>.)\n    <\/UL>\n<\/UL>\n<P>\nThat&#8217;s all there is to linking and unresolved externals.\nAt least, that&#8217;s all there is to the classical model.\n<\/P>\n<P>\nNext time, we&#8217;ll start looking at the consequences of the rules\nfor classical linking.\n<\/P>\n<P>\n<B>Sidebar<\/B>:\nModern linkers introduce lots of non-classical behavior.\nFor example,\nthe rule\n<\/P>\n<UL>\n<LI>If the symbol is already in the module marked as <I>resolved<\/I>,\n    then\n    <A HREF=\"http:\/\/msdn.microsoft.com\/library\/72zdcz6f.aspx\">\n    raise an error<\/A>\n    complaining that an object has multiple\n    definitions.\n<\/UL>\n<P>\nhas been replaced with the rules\n<\/P>\n<UL>\n<LI>If the symbol is already in the module marked as <I>resolved<\/I>:\n<UL>\n<LI>\n    If both the original symbol and the new symbol are marked\n    <CODE>__declspec(<A HREf=\"http:\/\/msdn.microsoft.com\/en-us\/library\/5tkz6s71.aspx\">selectany<\/A>)<\/CODE>,\n    then do not raise an error.\n    Pick one arbitrarily and discard the other.\n<LI>Otherwise,\n    <A HREF=\"http:\/\/msdn.microsoft.com\/library\/72zdcz6f.aspx\">\n    raise an error<\/A>\n    complaining that an object has multiple\n    definitions.\n<\/UL>\n<\/UL>\n<P>\nAnother example of non-classical behavior is\ndead code removal.\nIf you pass\n<A HREF=\"http:\/\/msdn.microsoft.com\/en-us\/library\/bxwfs976.aspx\">\nthe\n<CODE>\/OPT:REF<\/CODE> linker flag<\/A>,\nthen after all externals have been resolved,\nthe linker goes through and starts discarding functions and data\nthat are never referenced,\ntaking advantage of another non-classical feature\n(<A HREF=\"http:\/\/msdn.microsoft.com\/en-us\/library\/xsa71f43.aspx\">packed functions<\/A>)\nto know where each function begins and ends.\n<\/P>\n<P>\nBut I&#8217;m going to stick with the classical model,\nbecause you need to understand classical linking\nbefore you can study non-classical behavior.\nSort of how in physics, you need to learn your classical mechanics\nbefore you study relativity.\n<\/P><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The classical model for linking goes like this: Each OBJ file contains two lists of symbols. Provided symbols: These are symbols the OBJ contains definitions for. Needed symbols: These are symbols the OBJ would like the definitions for. (The official terms for these are exported and imported, but I will use provided and needed to [&hellip;]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25,131],"class_list":["post-5633","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code","tag-linker"],"acf":[],"blog_post_summary":"<p>The classical model for linking goes like this: Each OBJ file contains two lists of symbols. Provided symbols: These are symbols the OBJ contains definitions for. Needed symbols: These are symbols the OBJ would like the definitions for. (The official terms for these are exported and imported, but I will use provided and needed to [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/5633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=5633"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/5633\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=5633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=5633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=5633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}