ORDER AND JUDGMENT
Mary Beck Briscoe, Circuit Judge
After examining the brief and appellate record, this panel has determined unanimously that oral argument would not materially assist in the determination of this appeal. See Fed. R. App. P. 34(a)(2); 10th Cir. R. 34.1(G). The case is, therefore, ordered submitted without oral argument.
Tyrone Leslie Farris requests a certificate of appealability (COA) to appeal the district court’s order and judgment denying (in part as untimely and, in balance, on the merits) his petition for a writ of ha-beas corpus brought pursuant to 28 U.S.C. § 2241. Farris claims the State of Oklahoma is miscalculating his remaining prison sentence by failing to account for various credits to which he allegedly is entitled. He also claims that, for these and other reasons, the State lacks jurisdiction to continue his imprisonment. Farris additionally requests a COA to appeal the district court’s order denying his motion to [952]*952reconsider, filed pursuant to Federal Rule of Civil Procedure 60(b)(6). Also pending before us are his motions to proceed in forma pauperis (IFP) and for appointment of counsel.
We conclude the timeliness and merits of at least one of Farris’s claims are reasonably debatable, and therefore grant him a COA. However, Farris admits he has not exhausted applicable state court remedies. Consequently, exercising jurisdiction pursuant to 28 U.S.C. § 1291, we dismiss Farris’s petition for failure to exhaust. We grant Farris’s motion to proceed IFP, deny as moot his motion for appointment of counsel, and affirm the district court’s judgment, as modified to provide Farris with the opportunity to exhaust.
I. Background
In 1986, Farris was convicted by an Oklahoma jury of first-degree rape, for which he was sentenced to a 99-year term of imprisonment in the custody of the Oklahoma Department of Corrections (ODOC). In 2015, Farris filed this pro se § 2241 petition in the district court.1 Far-ris challenges as unconstitutional the manner in which the ODOC is executing his sentence, raising claims of two general types2 that, he alleges, require his “immediate discharge”- from custody. ROA at 47.
First, Farris claims the Constitution’s relevant proscription on ex post facto laws deprives Oklahoma of custody over him. See U.S. Const, art. I, § 10, cl. 1 (“No State shall ... pass any ... ex post facto law....”). In particular, Farris contends the State’s passage 'of the “Truth in Sentencing Act,” in 1997, and subsequent “repeal ]” of that purportedly “existing law[ ]” has had three alleged “ex post fac-to” effects on him. ROA at 14. By passing and repealing the Act (albeit before it was to take effect), Farris claims the State “commuted” his “disproportionate sentence and conviction” to a “maximum of 12 years,” id. at 18, which he claims to have served “completely.” Id. at 34. According to Farris, Oklahoma also “relinquished jurisdiction” and “custody” over him by passing and repealing the Act. Id. at 14. Finally, he contends the State’s legislative actions “rendered the judgment of execution” of his sentence “void,” id., and that “his judgment of conviction is void” as well. Id. at 32.
Second, Farris alleges that the ODOC has miscalculated various “earned credits,” id. at 75, he has accumulated toward the completion of his sentence, so much so that he would be entitled to “immediate discharge.” Id. at 47. More specifically, according to the ODOC’s records, Farris began his term of imprisonment with 35,999 days remaining on his sentence and a projected release date of March 4, 2084. Id. at 121. But “[i]n Oklahoma, with a few exceptions, inmates can earn credits towards reducing their term of imprisonment. Each earned credit is equivalent to one day of [953]*953incarceration.” Dulworth v. Evans, 442 F.3d 1265, 1266 n.2 (10th Cir. 2006) (citation omitted). Due to these credits, according to the ODOC, as of February 2016, Farris “had approximately 10,897 days left to serve.” ROA at 113.
However, Farris contends that the ODOC has significantly miscalculated his remaining sentence by failing to award him all of the credits he is due. In short, he claims also to be entitled to: 15 days of “achievement credits” for each month he was incarcerated from August 1985 until July 2014; “80 days per year for blood time credits”3; “Ekstrand”4 credits of “62 days per month” of incarceration; “statutory class level credits at level 4,” totaling “44 days per month” of incarceration; and “municipality” credits “at a rate of 3[ ]days for every day of work in the private” prison where he has been incarcerated since 1996. Id. at 38. Were Farris to receive all of these purportedly earned credits, his remaining sentence would be reduced by well over 50,000 days, entitling him to immediate release.
The ODOC submitted with its response to the petition summary records indicating that Farris was not awarded at least some of these credits that he claims to have earned. For example, he has never been awarded any blood time credits. In addition, the records indicate that at various times Farris was not awarded so-called Ekstrand credits, under Oklahoma’s old system for awarding credits, or class credits, under the State’s new system. See James v. Carr, 30 F.3d 141, 1994 WL 363542, at *2 (10th Cir. 1994) (unpublished) (“In essence, under the new scheme for applying credits[, a prisoner inearcerat-ed before the new system took effect] is receiving the best of both statutes, because whichever gives him the greatest amount determines the credits applied.”). Throughout 1992, for example, the ODOC did not award Farris either “pre-Ekst-rand” or “post-Ekstrand” credits. ROA at 22; see M. at 123 (summarizing the credits Farris was awarded in 1992).
In addition, Farris claims the ODOC “didn’t let [him] know” about these and other purported miscalculations. Id. at 78. For example, Farris claims that, “due to” the ODOC’s “poor record keeping,” the instances in which' he “gave blood” were not “documented,” such that he was “denied his statutory blood credits.” Id. at 159. He also claims that the ODOC “has hidden and suppressed” this information from him for years. Id.
Farris also contends that his “calendar days, earned credits and any additional days credited were not documented and not properly calculated.” Id. at 170. He also appears to argue that he was not given access to this “record card” or other “documentation” from which he could have determined that he was not being awarded all of the credits he is due. Id at 332. Indeed, the “record card,” id., itself contains no signature or other notation that Farris received a copy of it or was given access to it prior to the instant litigation, nor does any of the other evidence in this record so indicate.
In 2014 and 2015, Farris sent letters to ODOC officials challenging the purported failure to calculate correctly the length of his remaining sentence. He also filed sev[954]*954eral grievances and sent a letter to the Governor of Oklahoma detailing his concerns. He received no response to several of his letters. And though the ODOC awarded him certain additional credits for the period beginning as of the date of his grievances, it did not address his claims with respect to his previously earned but uncounted credits. Farris thus claims he has exhausted his administrative remedies.
However, Farris did not pursue relief in the Oklahoma courts prior to filing this petition. Indeed, among other things, thé ODOC argued that because Farris has “failed to exhaust his” claims “before an Oklahoma court,” his petition should be dismissed in its entirety. Id. at 114. Farris conveniently shifted his position in reply, arguing that he does “not seek immediate release” and, therefore, cannot seek relief in the Oklahoma courts. ECF No. 13 at 4, The district court accepted this disclaimer and concluded that, because Farris is not “asserting that he would be entitled to immediate release if he prevailed, there is no state judicial remedy” available to him. ECF No. 14 at 3. But to the contrary, as we will discuss, Farris can “seek habeas corpus relief’ in the State courts because, “if he is awarded all credits he contends are due to him, he will ... be entitled to immediate release....” Id. at 3-4.
To that end, rather than addressing the exhaustion issue, the district court denied on the merits Farris’s claims of entitlement to retroactive “achievement credits,” ROA at 323, and all of his claims that Oklahoma’s sentencing scheme operates as an ex post facto law with respect to him. The district court also denied as untimely Farris’s claims that he is entitled to “credits for blood donation, municipality credits and” so-called Ekstrand credits. Id. at 320. More specifically, in the district court’s view, Farris “would have ... received] reports of his release date and quarterly reports of his accumulated time,” from which he “could have easily discovered the factual predicate for” these claims years before he filed this petition. Id. at 321. As noted, however, Farris claims that the ODOC “should have,” but failed to, “notify] him of his entitlement to the credits” that the ODOC allegedly “failed to provide him.” Id. at 322 n.2. That is, Farris disputes that he received the reports of his earned credits, and no evidence in the record establishes when he first received them. In any event, the district court entered judgment to this effect on November 14, 2016.
Farris timely filed a notice of appeal. However, he contemporaneously filed in the district court an “Objection to the Order and Judgment,” id. at 327, in which, inter alia, he reiterated that there is no “proof’ that “notice was given to [him] by the” ODOC of his awarded credits. Id. at 332. He also requested that the district court issue him a “COA.” Id. at 333. We abated Farris’s attempt to appeal pending the outcome of the proceedings in the district court. See Fed. R. App. P. 4(a)(4)(B)(i).
The district court liberally construed Farris’s objection as a “timely motion for reconsideration,” ROA at 337; cf. Fed. R. Civ. P. 60(b)(6), which it further construed as raising only procedural challenges to its order denying the petition; Cf. Gonzalez v. Crosby, 646 U.S. 624, 634, 125 S.Ct. 2641, 162 L.Ed.2d 480 (2005) (“[A] Rule 60(b) motion that seeks to revisit the federal court’s denial on the merits of a claim for relief should be treated as a successive habeas petition.”). The district court denied the motion, though without passing on Farris’s request for a COA. In addition, the district court denied Farris’s separate motion for leave to proceed IFP on appeal.
Farris timely filed an amended notice of appeal. See Fed. R. App. P. 4(a)(4)(B)(ii). [955]*955We lifted the abatement, and Farris submitted a combined application for a COA and amended opening brief. Finally, as noted, Farris also filed motions for appointment of counsel and for leave to proceed IFP on appeal, both of which were referred to this panel for disposition with the request for a COA.
II. Analysis
A. COA
Before we can address the merits of Farris’s claims, we must determine whether we have jurisdiction over his appeal. Shepherd v. Holder, 678 F.3d 1171, 1180 (10th Cir. 2012); see also United States v. Ruiz, 536 U.S. 622, 628, 122 S.Ct. 2450, 153 L.Ed.2d 586 (2002) (explaining “a federal court always has jurisdiction to determine its own jurisdiction”). Specifically, “[a] state prisoner whose petition for a writ of habeas corpus is denied by a federal district court does not enjoy an absolute right to appeal. Federal law requires that he first obtain a COA from a circuit justice or judge.” Buck v. Davis, — U.S.-, 137 S.Ct. 759, 773, 197 L.Ed.2d 1 (2017) (citing 28 U.S.C. § 2253(c)(1)). “A COA may issue ‘only if the applicant has made a substantial showing of the denial of a constitutional right.’ ” Id. (quoting 28 U.S.C. § 2253(c)(2)). “Until the prisoner secures a COA, the Court of Appeals may not rule on the merits of his case.” Id. (citing Miller-El v. Cockrell, 537 U.S. 322, 336, 123 S.Ct. 1029, 154 L.Ed.2d 931 (2003)). Consequently, a “COA is a jurisdictional prerequisite to our review of a petition for a writ of habeas corpus.” United States v. Parker, 720 F.3d 781, 785 (10th Cir. 2013) (citing Miller-El, 537 U.S. at 336, 123 S.Ct. 1029); see Gonzalez v. Thaler, 565 U.S. 134, 142, 132 S.Ct. 641, 181 L.Ed.2d 619 (2012).
1.Appeal of the § 22⅛1 petition
As relevant here, a “petition brought under 28 U.S.C. § 2241 typically ‘attacks the execution of a sentence rather than its validity....’” Brace v. United States, 634 F.3d 1167, 1169 (10th Cir. 2011) (quoting Bradshaw v. Story, 86 F.3d 164, 166 (10th Cir. 1996)). In “this circuit, state prisoners ... may bring § 2241 habeas petitions” to “challeng[e] the execution of their sentence.” Stanko v. Davis, 617 F.3d 1262, 1268 (10th Cir. 2010), A state prisoner’s petition under § 2241 is subject to the relevant limitations imposed by the Anti-terrorism and Effective Death Penalty Act of 1996 (AEDPA), 28 U.S.C. § 2253(c)(1)(A). Burger v, Scott, 317 F.3d 1133, 1138-39 (10th Cir. 2003). We have therefore held that “a state prisoner seeking to appeal the denial of habeas relief in a § 2241 proceeding must obtain a COA to appeal.” Dulworth v. Jones, 496 F.3d 1133, 1135 (10th Cir. 2007) (citing Montez v. McKinna, 208 F.3d 862, 869 (10th Cir. 2000)). Thus, Farris requires a COA to challenge the district court’s denial of his § 2241 petition.
2.Appeal of the Rule 60(b) motion
Further, with respect to Farris’s “Objection to the Order and Judgment,” we agree with the district court that, construed liberally, his objections to the denial of his petition are focused on the alleged “hybrid” nature of the district court’s order. ROA at 327. A “COA is required to appeal from the denial of a true Rule 60(b) motion,” one raising such procedural objections. Spitznas v. Boone, 464 F.3d 1213, 1218 (10th Cir. 2006). Therefore, Farris also requires a COA to challenge the district court’s order denying his motion to reconsider. See Buck, 137 S.Ct. at 777.
3.The COA inquiry
In turn, “the COA inquiry,” the Supreme Court has “emphasized, is not coextensive with a merits analysis.” Id. at 773. [956]*956“At the COA-stage, the only question is whether the applicant has shown that ‘jurists of reason could disagree with the district court’s resolution of his constitutional claims or that jurists could conclude the issues presented are adequate to deserve encouragement to proceed further.’ ” Id. (quoting Miller-El, 537 U.S. at 327,123 S.Ct. 1029). “This threshold question should be decided without ‘full consideration of the factual or legal bases adduced in support of the claims.’” Id. (quoting Miller-El, 537 U.S. at 336, 123 S.Ct. 1029).
We cannot “sidestep” that inquiry “by first deciding the merits of an appeal” before determining whether a COA should issue, because “justifying [the] denial of a COA based on [the] adjudication of the actual merits ... is in essence deciding an appeal without jurisdiction.” Id (quoting Miller-El, 537 U.S. at 336-37, 123 S.Ct. 1029). When determining whether a COA should issue, we therefore must “‘limit [our] examination ... to a threshold inquiry into the underlying merit of [the] claims,’” under which we “ask ‘only if the’ ” district court’s “ ‘decision was debatable.’ ” Id. at 774 (quoting Miller-El, 537 U.S. at 327, 348, 123 S.Ct. 1029). A “claim can be debatable even though every jurist of reason might agree, after the COA has been granted and the case has received full consideration, that [the] petitioner will not prevail.” Id (quoting Miller-El, 537 U.S. at 338,123 S.Ct. 1029).
More specifically, the COA “standard is met when ‘reasonable jurists could debate whether (or, for that matter, agree that) the petition should have been resolved in a different manner.’ ” Welch v. United States, — U.S.-, 136 S.Ct. 1257, 1263, 194 L.Ed.2d 387 (2016) (quoting Slack v. McDaniel, 529 U.S. 473, 484, 120 S.Ct. 1595, 146 L.Ed.2d 542 (2000)). When “a district court has rejected the constitutional claims on the merits, the showing required to satisfy § 2253(c) is straightforward: The petitioner must demonstrate that reasonable jurists would find the district court’s assessment of the constitutional claims debatable or wrong.” Miller-El, 537 U.S. at 338, 123 S.Ct. 1029 (quoting Slack, 529 U.S. at 484, 120 S.Ct. 1595). This standard applies to Farris’s claims of ex post facto violations and for achievement credits. With respect to his other claims, however, a dual inquiry governs:
When, as here, the district court denies relief on procedural grounds, the petitioner seeking a COA must show both “that jurists of reason would find it debatable whether the petition states a valid claim of the denial of a constitutional right and that jurists of reason would find it debatable whether the district court was correct in its procedural ruling.”
Gonzalez, 565 U.S. at 140-41, 132 S.Ct. 641 (quoting Slack, 529 U.S. at 484, 120 S.Ct. 1595). Finally, because Farris’s challenge to the denial of his motion to reconsider “would be reviewed for abuse of discretion during a merits appeal,” the Supreme Court has accepted a formulation of “the COA question” as, “whether a reasonable jurist could conclude that the” district court “abused its discretion in declining to reopen the judgment.” Buck, 137 S.Ct. at 777 (accepting the parties’ agreed framing of this inquiry, and thus not deciding this question).
4. Farris is entitled to a COA
Applying those standards here, we conclude that Farris is entitled to a COA. Specifically, Farris alleges that he is entitled to receive credits each month under both the State of Oklahoma’s “pre-Ekst-rand” and “post-Ekstrand” systems. ROA at 22. Regardless of whether this is true, it is at least reasonably debatable whether Farris is entitled to receive credits under one of those systems every month that he [957]*957is incarcerated. However, the ODOC’s records made available to us indicate that, at least throughout 1992, he did not receive any credits under either system.. It is therefore reasonably debatable whether Farris’s petition states a valid claim of the denial of his alleged constitutional right to these credits. See Miller-El, 537 U.S. at 338, 123 S.Ct. 1029; Weaver v. Graham, 450 U.S. 24, 33-36, 101 S.Ct. 960, 67 L.Ed.2d 17 (1981).
Moreover, the district court’s procedural resolution of that claim is at least reasonably debatable because Farris contends that he was not provided the necessary documentation to discern that his credits were being undercounted, and the record does not refute this. See Gonzalez, 565 U.S. at 140-41, 132 S.Ct. 641; Evans, 442 F.3d at 1268. By the same measure, it is reasonably debatable whether the district court abused its discretion in refusing to reconsider these determinations. See Buck, 137 S.Ct. at 777.
Accordingly, we grant Farris a COA with respect to his claim that Oklahoma has miscalculated the number of so-called Ekstrand credits to which he is entitled. We therefore have jurisdiction over the district court’s judgment in this case. See Jennings v. Stephens, — U.S.-, 135 S.Ct. 793, 799, 190 L.Ed.2d 662 (2015).
B. Exhaustion
Turning to the merits, when “reviewing the denial of a habeas petition under § 2241, we review the district court’s legal conclusions de novo and accept its factual findings unless clearly erroneous.” al-Mar-ri v. Davis, 714 F.3d 1183, 1186 (10th Cir. 2013). Before proceeding to adjudicate the merits, however, Farris faces another procedural obstacle. “A state prisoner generally may not raise a claim for federal habe-as corpus relief unless he ‘has exhausted the remedies available in the courts of the State.’ ” Selsor v. Workman, 644 F.3d 984, 1026 (10th Cir. 2011) (quoting 28 U.S.C. § 2254(b)(1)(A)). We have held that this exhaustion requirement “is a prerequisite for § 2241 habeas relief, although we recognize that the statute itself does not expressly contain such a requirement.” Garza v. Davis, 596 F.3d 1198, 1203-04 (10th Cir. 2010).
“To exhaust a claim, a state prisoner must pursue it through ‘one complete round of the State’s established appellate review process,’ giving the state courts a ‘full and fair opportunity’ to correct alleged constitutional errors.” Selsor, 644 F.3d at 1026 (quoting O’Sullivan v. Boerckel, 526 U.S. 838, 845, 119 S.Ct. 1728, 144 L.Ed.2d 1 (1999)).
If a state prisoner has not properly exhausted state remedies, the federal courts ordinarily will not entertain an application for a writ of habeas corpus unless exhaustion would have been futile because either “there is an absence of available State corrective process” or “circumstances exist that render such process ineffective to protect the rights of the applicant.”
Id. (quoting 28 U.S.C. § 2254(b)(l)(B)(i)-(ii)). “The state prisoner bears the burden of proving that he exhausted state court remedies, or that exhaustion would have been futile.” Id (citations omitted). Of particular relevance here, “‘the fact that-[a] petitioner may have misunderstood or was confused about the procedural requirements provides no basis for equitable tolling,’ since ‘ignorance of the law, even for an incarcerated pro se petitioner, generally does not excuse’ ” such failures. Loftis v. Chrisman, 812 F.3d 1268, 1272 (10th Cir. 2016) (citations omitted).
Where we are faced with an unexhaust-ed or partially exhausted petition, unless we can deny all of the claims for other procedural reasons or on the merits, we [958]*958must dismiss the petition “without prejudice and allow” the petitioner “to return to state court to present the unexhausted claims to that court in the first instance.” Rhines v. Weber, 544 U.S. 269, 274, 125 S.Ct. 1528, 161 L.Ed.2d 440 (2005). That is, “individual, unexhausted claims may be denied, but only if the result allows the court to determine the entire petition on the merits.” Moore v. Schoeman, 288 F.3d 1231, 1235 (10th Cir. 2002). “The district court did not rely on” exhaustion to dismiss Farris’s “petition, but we are free to affirm on any ground for which there is a sufficient record to permit conclusions of law.” Grossman v. Bruce, 447 F.3d 801, 805 n.2 (10th Cir. 2006).
As discussed, Farris did not attempt to exhaust any of the claims in his § 2241 petition in the Oklahoma courts. He argues that doing so would have been futile. But that is simply not true, because (as he explicitly states in the petition) he is asserting several claims that, if shown to have merit, would entitle him to immediate release from custody, so the Oklahoma courts are open to him. See Canady v. Reynolds, 880 P.2d 391, 400 (Okla. Crim. App. 1994) (holding an Oklahoma prisoner “does not have a right to an interlocutory determination of the status of his earned credits in a situation where he is not entitled to immediate release,” but that a petition for a “writ of habeas corpus” in the Oklahoma courts “is appropriate ... at such time as he or she is entitled to immediate release”); see also Burger, 317 F.3d at 1135 (explaining that “Oklahoma imposes no time limits for filing applications for post-conviction relief in [its] district courts”). Finally, as noted, we are not in a position to deny all of Farris’s claims for another procedural reason or on the merits based on this record.
Therefore, like the district court, we conclude that Farris’s § 2241 petition must be dismissed. However, the dismissal should be without prejudice to provide Farris the opportunity to exhaust his remedies in the Oklahoma courts. But rather than vacating the district court’s judgment and remanding for it to perform that ministerial task, we will instead exercise our discretion to modify the judgment to operate without prejudice with respect to all of Farris’s claims. See 28 U.S.C. § 2106. So modified, we affirm the district court’s judgment dismissing Farris’s § 2241 petition and denying his motion to reconsider.
III. Conclusion
We GRANT Farris a COA to raise his claim that the State of Oklahoma has miscalculated his so-called Ekstrand credits. However, because Farris has failed to exhaust this and all of his other claims, we MODIFY the district court’s judgment to operate without prejudice so that he may exhaust his claims in the Oklahoma courts. So modified, we AFFIRM the dismissal of Farris’s § 2241 petition and the denial of his motion to reconsider. Accordingly, we GRANT Farris’s motion to proceed IFP on appeal and DENY AS MOOT his motion for appointment of counsel.
This order and judgment is not binding precedent, except under the doctrines of law of the case, res judicata, and collateral estoppel. It may be cited, however, for its persuasive value consistent with Fed. R. App, P. 32.1 and 10th Cir. R. 32.1.