This is an old revision of the document!
====== Todo: Audit the use of << and >> (shift) operators in gPXE ====== Per a discussion by mcb30: <code> [3:11pm] mcb30: rwcr: I am puzzled by this (1<<32) issue [3:11pm] mcb30: (I just replied to your e-mail) [3:12pm] ogreinside joined the chat room. [3:13pm] rwcr: Hmm. I didn't think about the overflow; that *should* make it work. [3:13pm] mcb30: It doesn't [3:13pm] rwcr: Aha. [3:13pm] mcb30: I just tested compiling the damn code [3:13pm] mcb30: I understand why the x86 code fails, but [3:13pm] rwcr: The x86 processor truncates CL to the bottom 5 bits when using it as the shift. [3:13pm] rwcr: So a shift by 32 turns into a shift by 0. [3:13pm] mcb30: Yes, but that is the kind of artefact that should not be visible at this level [3:14pm] mcb30: i.e. if x86 has that behaviour, but C says that << is a "pure" shift, then the compiler should insert a >=32 check on every shift [3:14pm] mdc: 32 mod 32 :) [3:14pm] mcb30: This must be mandated by the language spec somewhere [3:15pm] rwcr: I suspect it says shifts by more than the size of the variable have undefined or implementation-defined behavior. [3:15pm] mcb30: What concerns me is that I suspect I have relied on what I thought would be the correct behaviour in various bits of code over the years [3:16pm] mdc: https://www.securecoding.cert.org/confluence/display/seccode/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands [3:16pm] rwcr: "The results of some bitwise operations on signed integers" are implementation-defined. [3:16pm] mdc: (not quite the case here, but interesting) [3:16pm] rwcr: Try it with 1u << 32. [3:16pm] rwcr: C90 6.3, C95 6.5. [3:17pm] mcb30: I was using 1UL already in my test [3:17pm] rwcr: Eek. [3:18pm] rwcr: I get 0 for all types of 1 << (var == 32) shift. [3:18pm] mcb30: http://paste.etherboot.org:80/?page=view&id=1249931905 [3:19pm] mcb30: How are you forcing var to be variable (i.e. preventing the compiler optimising it to a constant shift)? [3:19pm] mcb30: (I made it a global variable to prevent this from happening) [3:19pm] rwcr: Ah, that'd be it - I used a local. [3:19pm] rwcr: Sure enough, turns out 1 now. [3:19pm] rwcr: This is rather scary. [3:20pm] mcb30: I found a mailing list post with the same problem, and someone saying that it is indeed undefined behaviour [3:21pm] rwcr: Disassembly shows a straight shl %cl,%eax without any checking. [3:21pm] rwcr: I think the behavior of that opcode changed on the 286 or so to truncate to 5 bits. [3:23pm] mcb30: 6.5.7 of C99 does indeed say "undefined" [3:23pm] mcb30: Hmmm [3:24pm] mcb30: I really don't feel like auditing every use of shift operators in the gPXE codebase [3:26pm] rwcr: There are 93 shifts by a variable count in gpxe.lkrn. [3:26pm] rwcr: Sorry, that's left shifts. 19 right shifts. [3:26pm] ogreinside1 joined the chat room. [3:26pm] MMlosh left the chat room. ("rebooting router to ensure proper configuration of readonly and readwrite paths") [3:26pm] mcb30: mdc_mobile: want something to do? ;) [3:27pm] • mdc suspects another "warnings purge" type of project :) [3:27pm] mdc: mcb30: I think we need an http://etherboot.org/wiki/todo page :) [3:27pm] mdc: With karma points for completing tasks therein :) [3:28pm] mcb30: Social solutions to technical problems :) [3:28pm] mdc: mcb30: Yes, since social beings need to do the work, it does often make sense :) [3:28pm] mdc: Ask the Chinese :) [3:29pm] mdc: Anyway, I take it we need to audit the use of << and >> in gPXE? [3:29pm] mcb30: Basically, yes [3:29pm] mcb30: Constant shifts are ok; the compiler already warns about those if they go out-of-range [3:30pm] mcb30: (which I thought was just it being helpful in the same vein as the "unsigned integer >= 0 is always true" warnings) [3:30pm] mdc: Can you make a page http://etherboot.org/wiki/todo/audit-the-shifts and describe the task so I can come back to it? (and perhaps make a link on http://etherboot.org/wiki/todo ? [3:31pm] mcb30: etherboot.org/wiki/todo doesn't exist [3:31pm] mcb30: (yet) [3:31pm] mdc: :) [3:31pm] • mdc likes dropping hints :) [3:31pm] mdc: hee hee [3:31pm] mcb30: That seems like a "project leader" type task to me [3:31pm] mdc: alright [3:32pm] mcb30: :) [3:32pm] mdc: lol [3:33pm] mcb30: I did my wiki-contributing for today already [3:33pm] mcb30: (documenting the SRP boot firmware table) [3:33pm] mdc: I'm making the ToDo page :) </code> Here is a list of all the variable shifts in gPXE, extracted with $ make clean $ make EXTRA_CFLAGS=-fno-inline bin/gpxe.lkrn $ objdump -d bin/gpxe.lkrn.tmp | grep "s[ah][lr].*%cl," | cut -d: -f1 | xargs addr2line -fe bin/gpxe.lkrn.tmp | \ perl -p0777e 's|\n/| @ /|g; s|'$PWD'/||g;' | uniq <code> corkscrew_probe1 @ drivers/net/3c515.c:727 read_eeprom @ drivers/net/davicom.c:398 read_eeprom @ drivers/net/davicom.c:407 read_srom_word @ drivers/net/dmfe.c:677 read_eeprom @ drivers/net/eepro.c:507 eepro100_poll @ drivers/net/eepro100.c:548 do_eeprom_cmd @ drivers/net/eepro100.c:353 eepro100_probe @ drivers/net/eepro100.c:646 mdio_clause45_wait_reset_mmds @ drivers/net/etherfabric.c:286 rtl8169_write_gmii_reg_bit @ drivers/net/r8169.c:348 rtl_poll @ drivers/net/rtl8139.c:426 sis900_read_eeprom @ drivers/net/sis900.c:478 sis900_mdio_read @ drivers/net/sis900.c:546 sky2_mhz @ drivers/net/sky2.c:1888 mdio_read @ drivers/net/sundance.c:813 mdio_write @ drivers/net/sundance.c:847 TLan_MiiSendData @ drivers/net/tlan.c:1189 mdio_read @ drivers/net/tulip.c:625 mdio_write @ drivers/net/tulip.c:684 read_eeprom @ drivers/net/tulip.c:712 read_eeprom @ drivers/net/tulip.c:723 WriteMII @ drivers/net/via-rhine.c:854 eeprom_read @ drivers/net/w89c840.c:753 mdio_read @ drivers/net/w89c840.c:817 w89c840_probe @ drivers/net/w89c840.c:676 e1000_get_hw_control @ drivers/net/e1000/e1000.c:68 e1000_mta_set @ drivers/net/e1000/e1000_hw.c:5883 e1000_rar_set @ drivers/net/e1000/e1000_hw.c:5941 e1000_clear_vfta @ drivers/net/e1000/e1000_hw.c:6013 e1000_blink_led_start @ drivers/net/e1000/e1000_hw.c:6189 e1000_blink_led_start @ drivers/net/e1000/e1000_hw.c:6191 e1000_shift_out_mdi_bits @ drivers/net/e1000/e1000_hw.c:3323 e1000_shift_out_ee_bits @ drivers/net/e1000/e1000_hw.c:4700 e1000_reset_hw @ drivers/net/e1000/e1000_hw.c:625 e1000_phy_reset @ drivers/net/e1000/e1000_hw.c:3918 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6066 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6071 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6077 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6078 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6084 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6088 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6094 e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6095 e1000_read_mac_addr @ drivers/net/e1000/e1000_hw.c:5729 e1000_init_eeprom_params @ drivers/net/e1000/e1000_hw.c:4637 phantom_check_boot_enable @ drivers/net/phantom/phantom.c:1944 phantom_poll_link_state @ drivers/net/phantom/phantom.c:1048 rtl8225_write @ drivers/net/rtl818x/rtl8185_rtl8225.c:74 rtl8225_read @ drivers/net/rtl818x/rtl8185_rtl8225.c:118 rtl8225_read @ drivers/net/rtl818x/rtl8185_rtl8225.c:178 ath5k_copy_channels @ drivers/net/ath5k/ath5k.c:571 ath5k_hw_start_tx_dma @ drivers/net/ath5k/ath5k_dma.c:146 ath5k_hw_set_txdp @ drivers/net/ath5k/ath5k_dma.c:309 ath5k_hw_stop_tx_dma @ drivers/net/ath5k/ath5k_dma.c:189 ath5k_eeprom_read_pcal_info_2413 @ drivers/net/ath5k/ath5k_eeprom.c:1215 ath5k_eeprom_read_pcal_info_5112 @ drivers/net/ath5k/ath5k_eeprom.c:958 ath5k_eeprom_convert_pcal_info_5111 @ drivers/net/ath5k/ath5k_eeprom.c:680 ath5k_hw_bitswap @ drivers/net/ath5k/ath5k.h:1269 ath5k_hw_rfb_op @ drivers/net/ath5k/ath5k_phy.c:108 ath5k_hw_rfb_op @ drivers/net/ath5k/ath5k_phy.c:113 ath5k_hw_rfb_op @ drivers/net/ath5k/ath5k_phy.c:114 ath5k_hw_rfb_op @ drivers/net/ath5k/ath5k_phy.c:116 ath5k_hw_reset_tx_queue @ drivers/net/ath5k/ath5k_qcu.c:187 ath5k_hw_reset_tx_queue @ drivers/net/ath5k/ath5k_qcu.c:189 ath5k_hw_write_ofdm_timings @ drivers/net/ath5k/ath5k_reset.c:129 nvs_read @ drivers/nvs/nvs.c:55 nvs_read @ drivers/nvs/nvs.c:69 nvs_write @ drivers/nvs/nvs.c:126 nvs_write @ drivers/nvs/nvs.c:144 threewire_detect_address_len @ drivers/nvs/threewire.c:121 i2c_select @ drivers/bitbash/i2c_bit.c:208 i2c_select @ drivers/bitbash/i2c_bit.c:216 spi_bit_transfer @ drivers/bitbash/spi_bit.c:107 icm_usage @ drivers/infiniband/arbel.c:1834 arbel_get_limits @ drivers/infiniband/arbel.c:1794 arbel_get_limits @ drivers/infiniband/arbel.c:1798 arbel_get_limits @ drivers/infiniband/arbel.c:1801 arbel_get_limits @ drivers/infiniband/arbel.c:1805 arbel_get_limits @ drivers/infiniband/arbel.c:1809 arbel_get_limits @ drivers/infiniband/arbel.c:1812 arbel_get_limits @ drivers/infiniband/arbel.c:1815 arbel_alloc_icm @ drivers/infiniband/arbel.c:1946 arbel_start_firmware @ drivers/infiniband/arbel.c:1713 icm_usage @ drivers/infiniband/hermon.c:2200 hermon_free_icm @ drivers/infiniband/hermon.c:2465 hermon_create_qp @ drivers/infiniband/hermon.c:976 hermon_get_cap @ drivers/infiniband/hermon.c:2156 hermon_get_cap @ drivers/infiniband/hermon.c:2161 hermon_get_cap @ drivers/infiniband/hermon.c:2164 hermon_get_cap @ drivers/infiniband/hermon.c:2169 hermon_get_cap @ drivers/infiniband/hermon.c:2172 linda_send_buf_in_use @ drivers/infiniband/linda.c:411 linda_create_recv_wq @ drivers/infiniband/linda.c:624 linda_create_recv_wq @ drivers/infiniband/linda.c:625 linda_destroy_recv_wq @ drivers/infiniband/linda.c:654 linda_destroy_recv_wq @ drivers/infiniband/linda.c:655 outb @ arch/i386/include/gpxe/x86_io.h:129 FD_SET @ include/gpxe/posix_io.h:49 base64_encode @ core/base64.c:59 bitmap_test @ core/bitmap.c:79 bitmap_set @ core/bitmap.c:95 isspace @ core/ctype.c:37 FD_ISSET @ include/gpxe/posix_io.h:72 fetch_uint_setting @ core/settings.c:707 net80211_set_rtscts_rate @ net/80211/net80211.c:1904 net80211_process_ie @ net/80211/net80211.c:1075 net80211_marshal_request_info @ net/80211/net80211.c:1207 rc80211_calc_net_goodness @ net/80211/rc80211.c:177 </code>
