README.unaligned-memory-access.txt 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240
  1. Editors note: This document is _heavily_ cribbed from the Linux Kernel, with
  2. really only the section about "Alignment vs. Networking" removed.
  3. UNALIGNED MEMORY ACCESSES
  4. =========================
  5. Linux runs on a wide variety of architectures which have varying behaviour
  6. when it comes to memory access. This document presents some details about
  7. unaligned accesses, why you need to write code that doesn't cause them,
  8. and how to write such code!
  9. The definition of an unaligned access
  10. =====================================
  11. Unaligned memory accesses occur when you try to read N bytes of data starting
  12. from an address that is not evenly divisible by N (i.e. addr % N != 0).
  13. For example, reading 4 bytes of data from address 0x10004 is fine, but
  14. reading 4 bytes of data from address 0x10005 would be an unaligned memory
  15. access.
  16. The above may seem a little vague, as memory access can happen in different
  17. ways. The context here is at the machine code level: certain instructions read
  18. or write a number of bytes to or from memory (e.g. movb, movw, movl in x86
  19. assembly). As will become clear, it is relatively easy to spot C statements
  20. which will compile to multiple-byte memory access instructions, namely when
  21. dealing with types such as u16, u32 and u64.
  22. Natural alignment
  23. =================
  24. The rule mentioned above forms what we refer to as natural alignment:
  25. When accessing N bytes of memory, the base memory address must be evenly
  26. divisible by N, i.e. addr % N == 0.
  27. When writing code, assume the target architecture has natural alignment
  28. requirements.
  29. In reality, only a few architectures require natural alignment on all sizes
  30. of memory access. However, we must consider ALL supported architectures;
  31. writing code that satisfies natural alignment requirements is the easiest way
  32. to achieve full portability.
  33. Why unaligned access is bad
  34. ===========================
  35. The effects of performing an unaligned memory access vary from architecture
  36. to architecture. It would be easy to write a whole document on the differences
  37. here; a summary of the common scenarios is presented below:
  38. - Some architectures are able to perform unaligned memory accesses
  39. transparently, but there is usually a significant performance cost.
  40. - Some architectures raise processor exceptions when unaligned accesses
  41. happen. The exception handler is able to correct the unaligned access,
  42. at significant cost to performance.
  43. - Some architectures raise processor exceptions when unaligned accesses
  44. happen, but the exceptions do not contain enough information for the
  45. unaligned access to be corrected.
  46. - Some architectures are not capable of unaligned memory access, but will
  47. silently perform a different memory access to the one that was requested,
  48. resulting in a subtle code bug that is hard to detect!
  49. It should be obvious from the above that if your code causes unaligned
  50. memory accesses to happen, your code will not work correctly on certain
  51. platforms and will cause performance problems on others.
  52. Code that does not cause unaligned access
  53. =========================================
  54. At first, the concepts above may seem a little hard to relate to actual
  55. coding practice. After all, you don't have a great deal of control over
  56. memory addresses of certain variables, etc.
  57. Fortunately things are not too complex, as in most cases, the compiler
  58. ensures that things will work for you. For example, take the following
  59. structure:
  60. struct foo {
  61. u16 field1;
  62. u32 field2;
  63. u8 field3;
  64. };
  65. Let us assume that an instance of the above structure resides in memory
  66. starting at address 0x10000. With a basic level of understanding, it would
  67. not be unreasonable to expect that accessing field2 would cause an unaligned
  68. access. You'd be expecting field2 to be located at offset 2 bytes into the
  69. structure, i.e. address 0x10002, but that address is not evenly divisible
  70. by 4 (remember, we're reading a 4 byte value here).
  71. Fortunately, the compiler understands the alignment constraints, so in the
  72. above case it would insert 2 bytes of padding in between field1 and field2.
  73. Therefore, for standard structure types you can always rely on the compiler
  74. to pad structures so that accesses to fields are suitably aligned (assuming
  75. you do not cast the field to a type of different length).
  76. Similarly, you can also rely on the compiler to align variables and function
  77. parameters to a naturally aligned scheme, based on the size of the type of
  78. the variable.
  79. At this point, it should be clear that accessing a single byte (u8 or char)
  80. will never cause an unaligned access, because all memory addresses are evenly
  81. divisible by one.
  82. On a related topic, with the above considerations in mind you may observe
  83. that you could reorder the fields in the structure in order to place fields
  84. where padding would otherwise be inserted, and hence reduce the overall
  85. resident memory size of structure instances. The optimal layout of the
  86. above example is:
  87. struct foo {
  88. u32 field2;
  89. u16 field1;
  90. u8 field3;
  91. };
  92. For a natural alignment scheme, the compiler would only have to add a single
  93. byte of padding at the end of the structure. This padding is added in order
  94. to satisfy alignment constraints for arrays of these structures.
  95. Another point worth mentioning is the use of __attribute__((packed)) on a
  96. structure type. This GCC-specific attribute tells the compiler never to
  97. insert any padding within structures, useful when you want to use a C struct
  98. to represent some data that comes in a fixed arrangement 'off the wire'.
  99. You might be inclined to believe that usage of this attribute can easily
  100. lead to unaligned accesses when accessing fields that do not satisfy
  101. architectural alignment requirements. However, again, the compiler is aware
  102. of the alignment constraints and will generate extra instructions to perform
  103. the memory access in a way that does not cause unaligned access. Of course,
  104. the extra instructions obviously cause a loss in performance compared to the
  105. non-packed case, so the packed attribute should only be used when avoiding
  106. structure padding is of importance.
  107. Code that causes unaligned access
  108. =================================
  109. With the above in mind, let's move onto a real life example of a function
  110. that can cause an unaligned memory access. The following function taken
  111. from the Linux Kernel's include/linux/etherdevice.h is an optimized routine
  112. to compare two ethernet MAC addresses for equality.
  113. bool ether_addr_equal(const u8 *addr1, const u8 *addr2)
  114. {
  115. #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
  116. u32 fold = ((*(const u32 *)addr1) ^ (*(const u32 *)addr2)) |
  117. ((*(const u16 *)(addr1 + 4)) ^ (*(const u16 *)(addr2 + 4)));
  118. return fold == 0;
  119. #else
  120. const u16 *a = (const u16 *)addr1;
  121. const u16 *b = (const u16 *)addr2;
  122. return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) == 0;
  123. #endif
  124. }
  125. In the above function, when the hardware has efficient unaligned access
  126. capability, there is no issue with this code. But when the hardware isn't
  127. able to access memory on arbitrary boundaries, the reference to a[0] causes
  128. 2 bytes (16 bits) to be read from memory starting at address addr1.
  129. Think about what would happen if addr1 was an odd address such as 0x10003.
  130. (Hint: it'd be an unaligned access.)
  131. Despite the potential unaligned access problems with the above function, it
  132. is included in the kernel anyway but is understood to only work normally on
  133. 16-bit-aligned addresses. It is up to the caller to ensure this alignment or
  134. not use this function at all. This alignment-unsafe function is still useful
  135. as it is a decent optimization for the cases when you can ensure alignment,
  136. which is true almost all of the time in ethernet networking context.
  137. Here is another example of some code that could cause unaligned accesses:
  138. void myfunc(u8 *data, u32 value)
  139. {
  140. [...]
  141. *((u32 *) data) = cpu_to_le32(value);
  142. [...]
  143. }
  144. This code will cause unaligned accesses every time the data parameter points
  145. to an address that is not evenly divisible by 4.
  146. In summary, the 2 main scenarios where you may run into unaligned access
  147. problems involve:
  148. 1. Casting variables to types of different lengths
  149. 2. Pointer arithmetic followed by access to at least 2 bytes of data
  150. Avoiding unaligned accesses
  151. ===========================
  152. The easiest way to avoid unaligned access is to use the get_unaligned() and
  153. put_unaligned() macros provided by the <asm/unaligned.h> header file.
  154. Going back to an earlier example of code that potentially causes unaligned
  155. access:
  156. void myfunc(u8 *data, u32 value)
  157. {
  158. [...]
  159. *((u32 *) data) = cpu_to_le32(value);
  160. [...]
  161. }
  162. To avoid the unaligned memory access, you would rewrite it as follows:
  163. void myfunc(u8 *data, u32 value)
  164. {
  165. [...]
  166. value = cpu_to_le32(value);
  167. put_unaligned(value, (u32 *) data);
  168. [...]
  169. }
  170. The get_unaligned() macro works similarly. Assuming 'data' is a pointer to
  171. memory and you wish to avoid unaligned access, its usage is as follows:
  172. u32 value = get_unaligned((u32 *) data);
  173. These macros work for memory accesses of any length (not just 32 bits as
  174. in the examples above). Be aware that when compared to standard access of
  175. aligned memory, using these macros to access unaligned memory can be costly in
  176. terms of performance.
  177. If use of such macros is not convenient, another option is to use memcpy(),
  178. where the source or destination (or both) are of type u8* or unsigned char*.
  179. Due to the byte-wise nature of this operation, unaligned accesses are avoided.
  180. --
  181. In the Linux Kernel,
  182. Authors: Daniel Drake <dsd@gentoo.org>,
  183. Johannes Berg <johannes@sipsolutions.net>
  184. With help from: Alan Cox, Avuton Olrich, Heikki Orsila, Jan Engelhardt,
  185. Kyle McMartin, Kyle Moffett, Randy Dunlap, Robert Hancock, Uli Kunitz,
  186. Vadim Lobanov