New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

item::charges is a long, but often used as an int #26103

Open
jbytheway opened this Issue Oct 6, 2018 · 15 comments

Comments

Projects
None yet
6 participants
@jbytheway
Contributor

jbytheway commented Oct 6, 2018

Describe the bug
(Arising from discussion in the largely unrelated PR #26092)

item::charges is a long, but many places working with charges only use an int. For example:

int vehicle::charge_battery( int amount, bool include_other_vehicles )

const int dropcount = items.size() * ( it.count_by_charges() ? it.charges : 1 );

const int qty = it.count_by_charges() ? std::min<int>( it.charges, count - obtained ) : 1;


int quantity = quantities.back();

static void move_item( item &it, int quantity, const tripoint &src, const tripoint &dest )

dropped.emplace_back( static_cast<int>( index ),

int amount = item_it->count_by_charges() ? item_it->charges : 1;

const int count = ( by_charges ) ? it.charges : sitem.stacks;

it->set_var( "remaining_water", static_cast<int>( water.charges ) );

I'm stopping after 10 examples; they were not difficult to find and I'm sure there are many more.

In practical terms, a long is an awkward data type to use because under MSVC on Windows it's the same as an int (32 bits) but on most other current platforms it's 64 bits. Since you have Appveyor CI set up using MSVC, I presume 32 bits is fine, and perhaps charges should just be made an int.

On the other hand, if item::charges really needs 64 bits then it should probably be int64_t, or maybe a custom type that doesn't implicitly cast to int.

I don't really think this will be a problem in practice (although #26031 might bring us a little closer to concern). But since @alanbrady raised it in review it felt appropriate to open an issue on the topic.

@cake-pie

This comment has been minimized.

Show comment
Hide comment
@cake-pie

cake-pie Oct 8, 2018

Contributor

I don't really think this will be a problem in practice (although #26031 might bring us a little closer to concern).

Not limited to #26031, there are several item stats that may be multiplied by number of charges, such as:

Cataclysm-DDA/src/itype.h

Lines 771 to 777 in 79d9903

units::mass weight = 0; // Weight for item ( or each stack member )
units::volume volume = 0; // Space occupied by items of this type
int price = 0; // Value before cataclysm
int price_post = -1; // Value after cataclysm (dependent upon practical usages)
int stack_size = 0; // Maximum identical items that can stack per above unit volume
units::volume integral_volume = units::from_milliliter(
-1 ); // Space consumed when integrated as part of another item (defaults to volume)

All of which have underlying type of int -- with volume in milliliters and mass in grams, so in theory overflow could occur. I'd concur that in practice it'll probably take some pretty absurd corner case before we get in trouble, but we may want to think about precautions nonetheless e.g. capping max number of charges in a stack, max values of weight/volume/price/etc per item.

Contributor

cake-pie commented Oct 8, 2018

I don't really think this will be a problem in practice (although #26031 might bring us a little closer to concern).

Not limited to #26031, there are several item stats that may be multiplied by number of charges, such as:

Cataclysm-DDA/src/itype.h

Lines 771 to 777 in 79d9903

units::mass weight = 0; // Weight for item ( or each stack member )
units::volume volume = 0; // Space occupied by items of this type
int price = 0; // Value before cataclysm
int price_post = -1; // Value after cataclysm (dependent upon practical usages)
int stack_size = 0; // Maximum identical items that can stack per above unit volume
units::volume integral_volume = units::from_milliliter(
-1 ); // Space consumed when integrated as part of another item (defaults to volume)

All of which have underlying type of int -- with volume in milliliters and mass in grams, so in theory overflow could occur. I'd concur that in practice it'll probably take some pretty absurd corner case before we get in trouble, but we may want to think about precautions nonetheless e.g. capping max number of charges in a stack, max values of weight/volume/price/etc per item.

@Xion350

This comment has been minimized.

Show comment
Hide comment
@Xion350

Xion350 Oct 10, 2018

I don't think there's any risk of overflow here. Even with mods that give you unlimited storage space.

Xion350 commented Oct 10, 2018

I don't think there's any risk of overflow here. Even with mods that give you unlimited storage space.

@Kelenius

This comment has been minimized.

Show comment
Hide comment
@Kelenius

Kelenius Oct 10, 2018

Contributor

32 thousand batteries in one place isn't impossible. They tend to spawn in stacks of 100, so it's just 320 stacks.

Contributor

Kelenius commented Oct 10, 2018

32 thousand batteries in one place isn't impossible. They tend to spawn in stacks of 100, so it's just 320 stacks.

@kevingranade

This comment has been minimized.

Show comment
Hide comment
@kevingranade

kevingranade Oct 10, 2018

Member

Max int isnt 32K, its 2 billion.

Member

kevingranade commented Oct 10, 2018

Max int isnt 32K, its 2 billion.

@Kelenius

This comment has been minimized.

Show comment
Hide comment
@Kelenius

Kelenius Oct 10, 2018

Contributor

Oh, right. In that case the highest likely number would probably be price of a battery stack: they cost 12000. There are more expensive items, but they're rare. 2147483647 / 12000 = 178956.971 so you'd need almost 179 thousand 100-battery stacks.

Contributor

Kelenius commented Oct 10, 2018

Oh, right. In that case the highest likely number would probably be price of a battery stack: they cost 12000. There are more expensive items, but they're rare. 2147483647 / 12000 = 178956.971 so you'd need almost 179 thousand 100-battery stacks.

@cake-pie

This comment has been minimized.

Show comment
Hide comment
@cake-pie

cake-pie Oct 10, 2018

Contributor

A map tile can accommodate up to 4096 different items and is capped at 1000L.
Assuming that's a safe upper limit in terms of how much space there is for items in a single place, and stack_size is fixed and working properly (see: #24929), then:

  • Largest stack size currently found in json is 1000, giving per-charge volume of 0.25mL. That means a theoretical 4,000,000 charges of, say, gold gold_small could be put in one map tile, which is well below max int.
  • Supposing we use int rather than long for item::charges, it would support max stack_size of 2^31 / (1000L/250mL) = 536,870, i.e. 1000L can hold max int charges of item having per-charge volume approx 0.466µL. That should be well beyond what we'd ever need -- the smallest volume I can imagine we'd care to measure is eyedrops at about 0.05mL per drop.

Which suggests int would suffice for item::charges.

For overflow avoidance (e.g. in #26031) stack size could be capped at around 2000 for a stack volume 250ml. That's 8,000,000 charges fits in 1000L, so (charges × stack_vol) / stack_size will see the numerator reach 2e9.

Contributor

cake-pie commented Oct 10, 2018

A map tile can accommodate up to 4096 different items and is capped at 1000L.
Assuming that's a safe upper limit in terms of how much space there is for items in a single place, and stack_size is fixed and working properly (see: #24929), then:

  • Largest stack size currently found in json is 1000, giving per-charge volume of 0.25mL. That means a theoretical 4,000,000 charges of, say, gold gold_small could be put in one map tile, which is well below max int.
  • Supposing we use int rather than long for item::charges, it would support max stack_size of 2^31 / (1000L/250mL) = 536,870, i.e. 1000L can hold max int charges of item having per-charge volume approx 0.466µL. That should be well beyond what we'd ever need -- the smallest volume I can imagine we'd care to measure is eyedrops at about 0.05mL per drop.

Which suggests int would suffice for item::charges.

For overflow avoidance (e.g. in #26031) stack size could be capped at around 2000 for a stack volume 250ml. That's 8,000,000 charges fits in 1000L, so (charges × stack_vol) / stack_size will see the numerator reach 2e9.

@jbytheway

This comment has been minimized.

Show comment
Hide comment
@jbytheway

jbytheway Oct 12, 2018

Contributor

If you have gold_small in a 250L cargo container as well as on the floor, you can have 5 million charges per map square. And when accumulating the charges available for crafting, all charges from map squares within a radius of 6 will be added together. That's at most 13x13=169 map squares (I think), meaning nearly 850 million charges total. There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite, which is only ~1e9. So in the most extreme case we're within about 20% of a potential problem.

Contributor

jbytheway commented Oct 12, 2018

If you have gold_small in a 250L cargo container as well as on the floor, you can have 5 million charges per map square. And when accumulating the charges available for crafting, all charges from map squares within a radius of 6 will be added together. That's at most 13x13=169 map squares (I think), meaning nearly 850 million charges total. There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite, which is only ~1e9. So in the most extreme case we're within about 20% of a potential problem.

@cake-pie

This comment has been minimized.

Show comment
Hide comment
@cake-pie

cake-pie Oct 12, 2018

Contributor

There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite

Hmm, that's bool item::merge_charges( const item &rhs )

Cataclysm-DDA/src/item.cpp

Lines 612 to 616 in c9e5e36

// Prevent overflow when either item has "near infinite" charges.
if( charges >= INFINITE_CHARGES / 2 || rhs.charges >= INFINITE_CHARGES / 2 ) {
charges = INFINITE_CHARGES;
return true;
}

By contrast, see void item::mod_charges( long mod )

Cataclysm-DDA/src/item.cpp

Lines 6784 to 6785 in c9e5e36

} else if( mod > 0 && charges >= INFINITE_CHARGES - mod ) {
charges = INFINITE_CHARGES - 1; // Highly unlikely, but finite charges should not become infinite.

The first doesn't actually look right; it's overzealous with the overflow prevention and potentially turns finite number of charges into infinite. (It'd also cause processing of item_counter in subsequent lines of code to be skipped unnecessarily for false positives of overflow detection.)

In practice it currently doesn't matter because no finite stacks get even close to these sizes.

If use int for charges then it'd become more important for that code to be correct; something like:

if( charges == INFINITE_CHARGES || rhs.charges == INFINITE_CHARGES ) {
    // merge finite stack into infinite stack, or two infinite stacks together
    charges = INFINITE_CHARGES;
    // process item_counter as sensibly as we can
    return true;
} else if ( rhs.charges > 0 && charges >= INFINITE_CHARGES - rhs.charges ) {
    // refuse to merge two finite stacks if it would lead to overflow
    // should not happen if item stats are kept within sane limits
    return false;
}

Continuing with the extreme worst conceivable case of combined number of charges within crafting range, 13×13=169 map squares with 1000L capacity on floor and 250L in vehicle storage can store 211250L.

211250 / (2^31-2) = 0.098371mL so we could support a per-charge volume of as low as 0.1mL if charges were int. [ (2^31-2) because INT_MAX reserved as special value INFINITE_CHARGES. ]

I was hoping for a minimum per-charge volume of 0.05mL (eyedrop dosage) but admittedly that's an outlier use case. (Unsigned int would do the trick, though!)

Contributor

cake-pie commented Oct 12, 2018

There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite

Hmm, that's bool item::merge_charges( const item &rhs )

Cataclysm-DDA/src/item.cpp

Lines 612 to 616 in c9e5e36

// Prevent overflow when either item has "near infinite" charges.
if( charges >= INFINITE_CHARGES / 2 || rhs.charges >= INFINITE_CHARGES / 2 ) {
charges = INFINITE_CHARGES;
return true;
}

By contrast, see void item::mod_charges( long mod )

Cataclysm-DDA/src/item.cpp

Lines 6784 to 6785 in c9e5e36

} else if( mod > 0 && charges >= INFINITE_CHARGES - mod ) {
charges = INFINITE_CHARGES - 1; // Highly unlikely, but finite charges should not become infinite.

The first doesn't actually look right; it's overzealous with the overflow prevention and potentially turns finite number of charges into infinite. (It'd also cause processing of item_counter in subsequent lines of code to be skipped unnecessarily for false positives of overflow detection.)

In practice it currently doesn't matter because no finite stacks get even close to these sizes.

If use int for charges then it'd become more important for that code to be correct; something like:

if( charges == INFINITE_CHARGES || rhs.charges == INFINITE_CHARGES ) {
    // merge finite stack into infinite stack, or two infinite stacks together
    charges = INFINITE_CHARGES;
    // process item_counter as sensibly as we can
    return true;
} else if ( rhs.charges > 0 && charges >= INFINITE_CHARGES - rhs.charges ) {
    // refuse to merge two finite stacks if it would lead to overflow
    // should not happen if item stats are kept within sane limits
    return false;
}

Continuing with the extreme worst conceivable case of combined number of charges within crafting range, 13×13=169 map squares with 1000L capacity on floor and 250L in vehicle storage can store 211250L.

211250 / (2^31-2) = 0.098371mL so we could support a per-charge volume of as low as 0.1mL if charges were int. [ (2^31-2) because INT_MAX reserved as special value INFINITE_CHARGES. ]

I was hoping for a minimum per-charge volume of 0.05mL (eyedrop dosage) but admittedly that's an outlier use case. (Unsigned int would do the trick, though!)

@Kelenius

This comment has been minimized.

Show comment
Hide comment
@Kelenius

Kelenius Oct 13, 2018

Contributor

Gold doesn't spawn often enough for this to be a problem in the first place.

Contributor

Kelenius commented Oct 13, 2018

Gold doesn't spawn often enough for this to be a problem in the first place.

@cake-pie

This comment has been minimized.

Show comment
Hide comment
@cake-pie

cake-pie Oct 13, 2018

Contributor

Sure, but it's prudent to to explore worst case scenarios so we can have strong guarantees in place and be pretty confident things aren't going to break if we switch to int or unsigned int.

Is there anything that contraindicates using unsigned for charges? I know item::mod_charges uses a signed parameter so it can be used for both adding and removing charges, but that's not a major blocker, I think?

Contributor

cake-pie commented Oct 13, 2018

Sure, but it's prudent to to explore worst case scenarios so we can have strong guarantees in place and be pretty confident things aren't going to break if we switch to int or unsigned int.

Is there anything that contraindicates using unsigned for charges? I know item::mod_charges uses a signed parameter so it can be used for both adding and removing charges, but that's not a major blocker, I think?

@jbytheway

This comment has been minimized.

Show comment
Hide comment
@jbytheway

jbytheway Oct 13, 2018

Contributor

I can think of a few reasons not to switch to unsigned:

  • People are bound to write code that in practice doesn't work for values greater than INT_MAX, and those bugs will almost certainly not be caught in testing.
  • Accidentally getting negative charges is entirely plausible to happen due to bugs, and it's helpful to be able to say with certainty that it was a bug, whereas with unsigned charges it's hard to distinguish underflow from really large numbers.
  • Signed integer overflow is undefined behaviour, and thus detectable with ubsan, should the game ever be run/tested with that. It would be nice to know that it would catch such bugs.
  • Whenever comparing charges with a signed number you'd have to agonise what kind of cast to use to avoid the compiler warning about signed/unsigned comparison.
Contributor

jbytheway commented Oct 13, 2018

I can think of a few reasons not to switch to unsigned:

  • People are bound to write code that in practice doesn't work for values greater than INT_MAX, and those bugs will almost certainly not be caught in testing.
  • Accidentally getting negative charges is entirely plausible to happen due to bugs, and it's helpful to be able to say with certainty that it was a bug, whereas with unsigned charges it's hard to distinguish underflow from really large numbers.
  • Signed integer overflow is undefined behaviour, and thus detectable with ubsan, should the game ever be run/tested with that. It would be nice to know that it would catch such bugs.
  • Whenever comparing charges with a signed number you'd have to agonise what kind of cast to use to avoid the compiler warning about signed/unsigned comparison.
@kevingranade

This comment has been minimized.

Show comment
Hide comment
@kevingranade

kevingranade Oct 14, 2018

Member

@jbytheway makes great points, unsigned integers are terrible for use as counting numbers. IMO they should be qvoided.

Member

kevingranade commented Oct 14, 2018

@jbytheway makes great points, unsigned integers are terrible for use as counting numbers. IMO they should be qvoided.

@cake-pie

This comment has been minimized.

Show comment
Hide comment
@cake-pie

cake-pie Oct 14, 2018

Contributor

Points taken re: unsigned.
Are we feeling comfortable with int then?

I'm thinking perhaps a couple checks could be added in Item_factory (check_definitions or finalize) to detect and warn about items whose stats may cause overflows in extreme circumstances:

  • number of charges in 211250L > INT_MAX
  • number of charges in 1000L × stat for stack_size charges > INT_MAX
    where stats to check are volume / integral_volume and price / price_postapoc
Contributor

cake-pie commented Oct 14, 2018

Points taken re: unsigned.
Are we feeling comfortable with int then?

I'm thinking perhaps a couple checks could be added in Item_factory (check_definitions or finalize) to detect and warn about items whose stats may cause overflows in extreme circumstances:

  • number of charges in 211250L > INT_MAX
  • number of charges in 1000L × stat for stack_size charges > INT_MAX
    where stats to check are volume / integral_volume and price / price_postapoc
@Kelenius

This comment has been minimized.

Show comment
Hide comment
@Kelenius

Kelenius Oct 14, 2018

Contributor

Maybe I'm saying a really stupid thing here, but are these checks really needed? The only way how this overflow could happen in the game is if you intentionally cause it by wishing for enough items, in which case you brought this upon yourself.

Contributor

Kelenius commented Oct 14, 2018

Maybe I'm saying a really stupid thing here, but are these checks really needed? The only way how this overflow could happen in the game is if you intentionally cause it by wishing for enough items, in which case you brought this upon yourself.

@kevingranade

This comment has been minimized.

Show comment
Hide comment
@kevingranade

kevingranade Oct 14, 2018

Member

The reason to put in a persistent check is so we're alerted if something happens like someone adding a "metal shavings" item with very high count that's produced by grinding up a car. I.e. a tiny volume item that gets produced in large quantities.

Member

kevingranade commented Oct 14, 2018

The reason to put in a persistent check is so we're alerted if something happens like someone adding a "metal shavings" item with very high count that's produced by grinding up a car. I.e. a tiny volume item that gets produced in large quantities.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment