Todo: Audit the use of << and >> (shift) operators in gPXE

Per a discussion by mcb30:

[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 :)

Here is a list of all the variable shifts in gPXE, extracted with

$ make veryclean
$ 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 | sort --field-separator=@ --key=2b

outb @ arch/i386/include/gpxe/x86_io.h:129
base64_encode @ core/base64.c:59
bitmap_test @ core/bitmap.c:79
bitmap_set @ core/bitmap.c:95
isspace @ core/ctype.c:37
fetch_uint_setting @ core/settings.c:707
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
arbel_start_firmware @ drivers/infiniband/arbel.c:1713
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
icm_usage @ drivers/infiniband/arbel.c:1834
arbel_alloc_icm @ drivers/infiniband/arbel.c:1946
hermon_bitmask_free @ drivers/infiniband/hermon.c:109
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
icm_usage @ drivers/infiniband/hermon.c:2200
hermon_free_icm @ drivers/infiniband/hermon.c:2465
hermon_create_qp @ drivers/infiniband/hermon.c:976
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
corkscrew_probe1 @ drivers/net/3c515.c:727
ath5k_copy_channels @ drivers/net/ath5k/ath5k.c:571
ath5k_hw_start_tx_dma @ drivers/net/ath5k/ath5k_dma.c:146
ath5k_hw_stop_tx_dma @ drivers/net/ath5k/ath5k_dma.c:189
ath5k_hw_set_txdp @ drivers/net/ath5k/ath5k_dma.c:309
ath5k_eeprom_read_pcal_info_2413 @ drivers/net/ath5k/ath5k_eeprom.c:1215
ath5k_eeprom_convert_pcal_info_5111 @ drivers/net/ath5k/ath5k_eeprom.c:680
ath5k_eeprom_read_pcal_info_5112 @ drivers/net/ath5k/ath5k_eeprom.c:958
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
read_eeprom @ drivers/net/davicom.c:398
read_eeprom @ drivers/net/davicom.c:407
read_srom_word @ drivers/net/dmfe.c:677
e1000_get_hw_control @ drivers/net/e1000/e1000.c:68
e1000_shift_out_mdi_bits @ drivers/net/e1000/e1000_hw.c:3323
e1000_phy_reset @ drivers/net/e1000/e1000_hw.c:3918
e1000_init_eeprom_params @ drivers/net/e1000/e1000_hw.c:4637
e1000_shift_out_ee_bits @ drivers/net/e1000/e1000_hw.c:4700
e1000_read_mac_addr @ drivers/net/e1000/e1000_hw.c:5729
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_id_led_init @ drivers/net/e1000/e1000_hw.c:6066
e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6072
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:6089
e1000_id_led_init @ drivers/net/e1000/e1000_hw.c:6095
e1000_blink_led_start @ drivers/net/e1000/e1000_hw.c:6189
e1000_blink_led_start @ drivers/net/e1000/e1000_hw.c:6191
e1000_reset_hw @ drivers/net/e1000/e1000_hw.c:625
do_eeprom_cmd @ drivers/net/eepro100.c:353
eepro100_poll @ drivers/net/eepro100.c:548
eepro100_probe @ drivers/net/eepro100.c:646
read_eeprom @ drivers/net/eepro.c:507
mdio_clause45_wait_reset_mmds @ drivers/net/etherfabric.c:286
phantom_poll_link_state @ drivers/net/phantom/phantom.c:1048
phantom_check_boot_enable @ drivers/net/phantom/phantom.c:1944
rtl8169_write_gmii_reg_bit @ drivers/net/r8169.c:348
rtl_poll @ drivers/net/rtl8139.c:426
rtl8225_read @ drivers/net/rtl818x/rtl8185_rtl8225.c:118
rtl8225_read @ drivers/net/rtl818x/rtl8185_rtl8225.c:178
rtl8225_write @ drivers/net/rtl818x/rtl8185_rtl8225.c:74
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
w89c840_probe @ drivers/net/w89c840.c:676
eeprom_read @ drivers/net/w89c840.c:753
mdio_read @ drivers/net/w89c840.c:817
nvs_write @ drivers/nvs/nvs.c:126
nvs_write @ drivers/nvs/nvs.c:144
nvs_read @ drivers/nvs/nvs.c:55
nvs_read @ drivers/nvs/nvs.c:69
threewire_detect_address_len @ drivers/nvs/threewire.c:121
FD_SET @ include/gpxe/posix_io.h:49
FD_ISSET @ include/gpxe/posix_io.h:72
net80211_process_ie @ net/80211/net80211.c:1075
net80211_marshal_request_info @ net/80211/net80211.c:1207
net80211_set_rtscts_rate @ net/80211/net80211.c:1904
rc80211_calc_net_goodness @ net/80211/rc80211.c:177