diff --git a/android/apex.go b/android/apex.go
index 30152db..47f07ca 100644
--- a/android/apex.go
+++ b/android/apex.go
@@ -124,6 +124,10 @@
 	// the private part of the listed APEXes even when it is not included in the
 	// APEXes.
 	TestFor() []string
+
+	// Returns nil if this module supports sdkVersion
+	// Otherwise, returns error with reason
+	ShouldSupportSdkVersion(ctx BaseModuleContext, sdkVersion int) error
 }
 
 type ApexProperties struct {
@@ -477,3 +481,125 @@
 		},
 	})
 }
+
+// TODO(b/158059172): remove minSdkVersion allowlist
+var minSdkVersionAllowlist = map[string]int{
+	"adbd":                  30,
+	"android.net.ipsec.ike": 30,
+	"androidx-constraintlayout_constraintlayout-solver": 30,
+	"androidx.annotation_annotation":                    28,
+	"androidx.arch.core_core-common":                    28,
+	"androidx.collection_collection":                    28,
+	"androidx.lifecycle_lifecycle-common":               28,
+	"apache-commons-compress":                           29,
+	"bouncycastle_ike_digests":                          30,
+	"brotli-java":                                       29,
+	"captiveportal-lib":                                 28,
+	"flatbuffer_headers":                                30,
+	"framework-permission":                              30,
+	"framework-statsd":                                  30,
+	"gemmlowp_headers":                                  30,
+	"ike-internals":                                     30,
+	"kotlinx-coroutines-android":                        28,
+	"kotlinx-coroutines-core":                           28,
+	"libadb_crypto":                                     30,
+	"libadb_pairing_auth":                               30,
+	"libadb_pairing_connection":                         30,
+	"libadb_pairing_server":                             30,
+	"libadb_protos":                                     30,
+	"libadb_tls_connection":                             30,
+	"libadbconnection_client":                           30,
+	"libadbconnection_server":                           30,
+	"libadbd_core":                                      30,
+	"libadbd_services":                                  30,
+	"libadbd":                                           30,
+	"libapp_processes_protos_lite":                      30,
+	"libasyncio":                                        30,
+	"libbrotli":                                         30,
+	"libbuildversion":                                   30,
+	"libcrypto_static":                                  30,
+	"libcrypto_utils":                                   30,
+	"libdiagnose_usb":                                   30,
+	"libeigen":                                          30,
+	"liblz4":                                            30,
+	"libmdnssd":                                         30,
+	"libneuralnetworks_common":                          30,
+	"libneuralnetworks_headers":                         30,
+	"libneuralnetworks":                                 30,
+	"libprocpartition":                                  30,
+	"libprotobuf-java-lite":                             30,
+	"libprotoutil":                                      30,
+	"libqemu_pipe":                                      30,
+	"libstats_jni":                                      30,
+	"libstatslog_statsd":                                30,
+	"libstatsmetadata":                                  30,
+	"libstatspull":                                      30,
+	"libstatssocket":                                    30,
+	"libsync":                                           30,
+	"libtextclassifier_hash_headers":                    30,
+	"libtextclassifier_hash_static":                     30,
+	"libtflite_kernel_utils":                            30,
+	"libwatchdog":                                       29,
+	"libzstd":                                           30,
+	"metrics-constants-protos":                          28,
+	"net-utils-framework-common":                        29,
+	"permissioncontroller-statsd":                       28,
+	"philox_random_headers":                             30,
+	"philox_random":                                     30,
+	"service-permission":                                30,
+	"service-statsd":                                    30,
+	"statsd-aidl-ndk_platform":                          30,
+	"statsd":                                            30,
+	"tensorflow_headers":                                30,
+	"xz-java":                                           29,
+}
+
+// Function called while walking an APEX's payload dependencies.
+//
+// Return true if the `to` module should be visited, false otherwise.
+type PayloadDepsCallback func(ctx ModuleContext, from blueprint.Module, to ApexModule, externalDep bool) bool
+
+// UpdatableModule represents updatable APEX/APK
+type UpdatableModule interface {
+	Module
+	WalkPayloadDeps(ctx ModuleContext, do PayloadDepsCallback)
+}
+
+// CheckMinSdkVersion checks if every dependency of an updatable module sets min_sdk_version accordingly
+func CheckMinSdkVersion(m UpdatableModule, ctx ModuleContext, minSdkVersion int) {
+	// do not enforce min_sdk_version for host
+	if ctx.Host() {
+		return
+	}
+
+	// do not enforce for coverage build
+	if ctx.Config().IsEnvTrue("EMMA_INSTRUMENT") || ctx.DeviceConfig().NativeCoverageEnabled() || ctx.DeviceConfig().ClangCoverageEnabled() {
+		return
+	}
+
+	// do not enforce deps.min_sdk_version if APEX/APK doesn't set min_sdk_version or
+	// min_sdk_version is not finalized (e.g. current or codenames)
+	if minSdkVersion == FutureApiLevel {
+		return
+	}
+
+	m.WalkPayloadDeps(ctx, func(ctx ModuleContext, from blueprint.Module, to ApexModule, externalDep bool) bool {
+		if externalDep {
+			// external deps are outside the payload boundary, which is "stable" interface.
+			// We don't have to check min_sdk_version for external dependencies.
+			return false
+		}
+		if am, ok := from.(DepIsInSameApex); ok && !am.DepIsInSameApex(ctx, to) {
+			return false
+		}
+		if err := to.ShouldSupportSdkVersion(ctx, minSdkVersion); err != nil {
+			toName := ctx.OtherModuleName(to)
+			if ver, ok := minSdkVersionAllowlist[toName]; !ok || ver > minSdkVersion {
+				ctx.OtherModuleErrorf(to, "should support min_sdk_version(%v) for %q: %v. Dependency path: %s",
+					minSdkVersion, ctx.ModuleName(), err.Error(), ctx.GetPathString(false))
+				return false
+			}
+		}
+		return true
+	})
+}
diff --git a/apex/apex.go b/apex/apex.go
index e308d48..6ab58c9 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -1725,13 +1725,8 @@
 	return true
 }
 
-// Function called while walking an APEX's payload dependencies.
-//
-// Return true if the `to` module should be visited, false otherwise.
-type payloadDepsCallback func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool
-
 // Visit dependencies that contributes to the payload of this APEX
-func (a *apexBundle) walkPayloadDeps(ctx android.ModuleContext, do payloadDepsCallback) {
+func (a *apexBundle) WalkPayloadDeps(ctx android.ModuleContext, do android.PayloadDepsCallback) {
 	ctx.WalkDeps(func(child, parent android.Module) bool {
 		am, ok := child.(android.ApexModule)
 		if !ok || !am.CanHaveApexVariants() {
@@ -1757,7 +1752,21 @@
 }
 
 func (a *apexBundle) minSdkVersion(ctx android.BaseModuleContext) int {
-	ver := proptools.StringDefault(a.properties.Min_sdk_version, "current")
+	ver := proptools.String(a.properties.Min_sdk_version)
+	if ver == "" {
+		return android.FutureApiLevel
+	}
+	// Treat the current codenames as "current", which means future API version (10000)
+	// Otherwise, ApiStrToNum converts codename(non-finalized) to a value from [9000...]
+	// and would fail to build against "current".
+	if android.InList(ver, ctx.Config().PlatformVersionActiveCodenames()) {
+		return android.FutureApiLevel
+	}
+	// In "REL" branch, "current" is mapped to finalized sdk version
+	if ctx.Config().PlatformSdkCodename() == "REL" && ver == "current" {
+		return ctx.Config().PlatformSdkVersionInt()
+	}
+	// Finalized codenames are OKAY and will be converted to int
 	intVer, err := android.ApiStrToNum(ctx, ver)
 	if err != nil {
 		ctx.PropertyErrorf("min_sdk_version", "%s", err.Error())
@@ -1785,7 +1794,7 @@
 		return
 	}
 
-	a.walkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
+	a.WalkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
 		if externalDep {
 			// As soon as the dependency graph crosses the APEX boundary, don't go further.
 			return false
@@ -1821,6 +1830,17 @@
 	}
 }
 
+func (a *apexBundle) checkMinSdkVersion(ctx android.ModuleContext) {
+	if a.testApex || a.vndkApex {
+		return
+	}
+	// Meaningless to check min_sdk_version when building use_vendor modules against non-Trebleized targets
+	if proptools.Bool(a.properties.Use_vendor) && ctx.DeviceConfig().VndkVersion() == "" {
+		return
+	}
+	android.CheckMinSdkVersion(a, ctx, a.minSdkVersion(ctx))
+}
+
 // Ensures that a lib providing stub isn't statically linked
 func (a *apexBundle) checkStaticLinkingToStubLibraries(ctx android.ModuleContext) {
 	// Practically, we only care about regular APEXes on the device.
@@ -1828,7 +1848,7 @@
 		return
 	}
 
-	a.walkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
+	a.WalkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
 		if ccm, ok := to.(*cc.Module); ok {
 			apexName := ctx.ModuleName()
 			fromName := ctx.OtherModuleName(from)
@@ -1903,6 +1923,7 @@
 
 	a.checkApexAvailability(ctx)
 	a.checkUpdatable(ctx)
+	a.checkMinSdkVersion(ctx)
 	a.checkStaticLinkingToStubLibraries(ctx)
 
 	handleSpecialLibs := !android.Bool(a.properties.Ignore_system_library_special_case)
@@ -1936,7 +1957,7 @@
 	})
 
 	var filesInfo []apexFile
-	// TODO(jiyong) do this using walkPayloadDeps
+	// TODO(jiyong) do this using WalkPayloadDeps
 	ctx.WalkDepsBlueprint(func(child, parent blueprint.Module) bool {
 		depTag := ctx.OtherModuleDependencyTag(child)
 		if _, ok := depTag.(android.ExcludeFromApexContentsTag); ok {
diff --git a/apex/apex_test.go b/apex/apex_test.go
index 3d5886e..e0b19f4 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -206,6 +206,7 @@
 	config.TestProductVariables.CertificateOverrides = []string{"myapex_keytest:myapex.certificate.override"}
 	config.TestProductVariables.Platform_sdk_codename = proptools.StringPtr("Q")
 	config.TestProductVariables.Platform_sdk_final = proptools.BoolPtr(false)
+	config.TestProductVariables.Platform_version_active_codenames = []string{"R"}
 	config.TestProductVariables.Platform_vndk_version = proptools.StringPtr("VER")
 
 	for _, handler := range handlers {
@@ -1104,13 +1105,13 @@
 	}{
 		{
 			name:          "should link to the latest",
-			minSdkVersion: "current",
+			minSdkVersion: "",
 			shouldLink:    "30",
 			shouldNotLink: []string{"29"},
 		},
 		{
 			name:          "should link to llndk#29",
-			minSdkVersion: "29",
+			minSdkVersion: "min_sdk_version: \"29\",",
 			shouldLink:    "29",
 			shouldNotLink: []string{"30"},
 		},
@@ -1123,7 +1124,7 @@
 				key: "myapex.key",
 				use_vendor: true,
 				native_shared_libs: ["mylib"],
-				min_sdk_version: "`+tc.minSdkVersion+`",
+				`+tc.minSdkVersion+`
 			}
 
 			apex_key {
@@ -1140,6 +1141,7 @@
 				system_shared_libs: [],
 				stl: "none",
 				apex_available: [ "myapex" ],
+				min_sdk_version: "29",
 			}
 
 			cc_library {
@@ -1270,24 +1272,24 @@
 	ensureContains(t, libFlags, "libdl/android_arm64_armv8-a_shared/libdl.so")
 }
 
-func TestApexUseStubsAccordingToMinSdkVersionInUnbundledBuild(t *testing.T) {
+func TestApexMinSdkVersion_NativeModulesShouldBeBuiltAgainstStubs(t *testing.T) {
 	// there are three links between liba --> libz
-	// 1) myapex -> libx -> liba -> libz    : this should be #2 link, but fallback to #1
-	// 2) otherapex -> liby -> liba -> libz : this should be #3 link
+	// 1) myapex -> libx -> liba -> libz    : this should be #29 link, but fallback to #28
+	// 2) otherapex -> liby -> liba -> libz : this should be #30 link
 	// 3) (platform) -> liba -> libz        : this should be non-stub link
 	ctx, _ := testApex(t, `
 		apex {
 			name: "myapex",
 			key: "myapex.key",
 			native_shared_libs: ["libx"],
-			min_sdk_version: "2",
+			min_sdk_version: "29",
 		}
 
 		apex {
 			name: "otherapex",
 			key: "myapex.key",
 			native_shared_libs: ["liby"],
-			min_sdk_version: "3",
+			min_sdk_version: "30",
 		}
 
 		apex_key {
@@ -1302,6 +1304,7 @@
 			system_shared_libs: [],
 			stl: "none",
 			apex_available: [ "myapex" ],
+			min_sdk_version: "29",
 		}
 
 		cc_library {
@@ -1310,6 +1313,7 @@
 			system_shared_libs: [],
 			stl: "none",
 			apex_available: [ "otherapex" ],
+			min_sdk_version: "29",
 		}
 
 		cc_library {
@@ -1321,6 +1325,7 @@
 				"//apex_available:anyapex",
 				"//apex_available:platform",
 			],
+			min_sdk_version: "29",
 		}
 
 		cc_library {
@@ -1328,10 +1333,10 @@
 			system_shared_libs: [],
 			stl: "none",
 			stubs: {
-				versions: ["1", "3"],
+				versions: ["28", "30"],
 			},
 		}
-	`, withUnbundledBuild)
+	`)
 
 	expectLink := func(from, from_variant, to, to_variant string) {
 		ldArgs := ctx.ModuleForTests(from, "android_arm64_armv8-a_"+from_variant).Rule("ld").Args["libFlags"]
@@ -1343,13 +1348,13 @@
 	}
 	// platform liba is linked to non-stub version
 	expectLink("liba", "shared", "libz", "shared")
-	// liba in myapex is linked to #1
-	expectLink("liba", "shared_myapex", "libz", "shared_1")
-	expectNoLink("liba", "shared_myapex", "libz", "shared_3")
+	// liba in myapex is linked to #28
+	expectLink("liba", "shared_myapex", "libz", "shared_28")
+	expectNoLink("liba", "shared_myapex", "libz", "shared_30")
 	expectNoLink("liba", "shared_myapex", "libz", "shared")
-	// liba in otherapex is linked to #3
-	expectLink("liba", "shared_otherapex", "libz", "shared_3")
-	expectNoLink("liba", "shared_otherapex", "libz", "shared_1")
+	// liba in otherapex is linked to #30
+	expectLink("liba", "shared_otherapex", "libz", "shared_30")
+	expectNoLink("liba", "shared_otherapex", "libz", "shared_28")
 	expectNoLink("liba", "shared_otherapex", "libz", "shared")
 }
 
@@ -1374,6 +1379,7 @@
 			system_shared_libs: [],
 			stl: "none",
 			apex_available: [ "myapex" ],
+			min_sdk_version: "R",
 		}
 
 		cc_library {
@@ -1407,7 +1413,7 @@
 	expectNoLink("libx", "shared_myapex", "libz", "shared")
 }
 
-func TestApexMinSdkVersionDefaultsToLatest(t *testing.T) {
+func TestApexMinSdkVersion_DefaultsToLatest(t *testing.T) {
 	ctx, _ := testApex(t, `
 		apex {
 			name: "myapex",
@@ -1516,6 +1522,7 @@
 			name: "libx",
 			shared_libs: ["libbar"],
 			apex_available: [ "myapex" ],
+			min_sdk_version: "29",
 		}
 
 		cc_library {
@@ -1553,6 +1560,7 @@
 		cc_library {
 			name: "libx",
 			apex_available: [ "myapex" ],
+			min_sdk_version: "29",
 		}
 	`)
 
@@ -1564,7 +1572,7 @@
 	ensureListNotContains(t, cm.Properties.AndroidMkStaticLibs, "libgcc_stripped")
 }
 
-func TestInvalidMinSdkVersion(t *testing.T) {
+func TestApexMinSdkVersion_ErrorIfIncompatibleStubs(t *testing.T) {
 	testApexError(t, `"libz" .*: not found a version\(<=29\)`, `
 		apex {
 			name: "myapex",
@@ -1585,6 +1593,7 @@
 			system_shared_libs: [],
 			stl: "none",
 			apex_available: [ "myapex" ],
+			min_sdk_version: "29",
 		}
 
 		cc_library {
@@ -1596,12 +1605,15 @@
 			},
 		}
 	`)
+}
 
-	testApexError(t, `"myapex" .*: min_sdk_version: SDK version should be .*`, `
+func TestApexMinSdkVersion_ErrorIfIncompatibleVersion(t *testing.T) {
+	testApexError(t, `module "mylib".*: should support min_sdk_version\(29\)`, `
 		apex {
 			name: "myapex",
 			key: "myapex.key",
-			min_sdk_version: "abc",
+			native_shared_libs: ["mylib"],
+			min_sdk_version: "29",
 		}
 
 		apex_key {
@@ -1609,6 +1621,67 @@
 			public_key: "testkey.avbpubkey",
 			private_key: "testkey.pem",
 		}
+
+		cc_library {
+			name: "mylib",
+			srcs: ["mylib.cpp"],
+			system_shared_libs: [],
+			stl: "none",
+			apex_available: [
+				"myapex",
+			],
+			min_sdk_version: "30",
+		}
+	`)
+}
+
+func TestApexMinSdkVersion_Okay(t *testing.T) {
+	testApex(t, `
+		apex {
+			name: "myapex",
+			key: "myapex.key",
+			native_shared_libs: ["libfoo"],
+			java_libs: ["libbar"],
+			min_sdk_version: "29",
+		}
+
+		apex_key {
+			name: "myapex.key",
+			public_key: "testkey.avbpubkey",
+			private_key: "testkey.pem",
+		}
+
+		cc_library {
+			name: "libfoo",
+			srcs: ["mylib.cpp"],
+			shared_libs: ["libfoo_dep"],
+			apex_available: ["myapex"],
+			min_sdk_version: "29",
+		}
+
+		cc_library {
+			name: "libfoo_dep",
+			srcs: ["mylib.cpp"],
+			apex_available: ["myapex"],
+			min_sdk_version: "29",
+		}
+
+		java_library {
+			name: "libbar",
+			sdk_version: "current",
+			srcs: ["a.java"],
+			static_libs: ["libbar_dep"],
+			apex_available: ["myapex"],
+			min_sdk_version: "29",
+		}
+
+		java_library {
+			name: "libbar_dep",
+			sdk_version: "current",
+			srcs: ["a.java"],
+			apex_available: ["myapex"],
+			min_sdk_version: "29",
+		}
 	`)
 }
 
@@ -1659,6 +1732,7 @@
 					srcs: ["foo/bar/MyClass.java"],
 					sdk_version: "current",
 					apex_available: ["myapex"],
+					min_sdk_version: "29",
 				}
 			`,
 		},
@@ -1728,6 +1802,135 @@
 	}
 }
 
+func TestApexMinSdkVersion_ErrorIfDepIsNewer(t *testing.T) {
+	testApexError(t, `module "mylib2".*: should support min_sdk_version\(29\) for "myapex"`, `
+		apex {
+			name: "myapex",
+			key: "myapex.key",
+			native_shared_libs: ["mylib"],
+			min_sdk_version: "29",
+		}
+
+		apex_key {
+			name: "myapex.key",
+			public_key: "testkey.avbpubkey",
+			private_key: "testkey.pem",
+		}
+
+		cc_library {
+			name: "mylib",
+			srcs: ["mylib.cpp"],
+			shared_libs: ["mylib2"],
+			system_shared_libs: [],
+			stl: "none",
+			apex_available: [
+				"myapex",
+			],
+			min_sdk_version: "29",
+		}
+
+		// indirect part of the apex
+		cc_library {
+			name: "mylib2",
+			srcs: ["mylib.cpp"],
+			system_shared_libs: [],
+			stl: "none",
+			apex_available: [
+				"myapex",
+			],
+			min_sdk_version: "30",
+		}
+	`)
+}
+
+func TestApexMinSdkVersion_ErrorIfDepIsNewer_Java(t *testing.T) {
+	testApexError(t, `module "bar".*: should support min_sdk_version\(29\) for "myapex"`, `
+		apex {
+			name: "myapex",
+			key: "myapex.key",
+			apps: ["AppFoo"],
+			min_sdk_version: "29",
+		}
+
+		apex_key {
+			name: "myapex.key",
+			public_key: "testkey.avbpubkey",
+			private_key: "testkey.pem",
+		}
+
+		android_app {
+			name: "AppFoo",
+			srcs: ["foo/bar/MyClass.java"],
+			sdk_version: "current",
+			min_sdk_version: "29",
+			system_modules: "none",
+			stl: "none",
+			static_libs: ["bar"],
+			apex_available: [ "myapex" ],
+		}
+
+		java_library {
+			name: "bar",
+			sdk_version: "current",
+			srcs: ["a.java"],
+			apex_available: [ "myapex" ],
+		}
+	`)
+}
+
+func TestApexMinSdkVersion_OkayEvenWhenDepIsNewer_IfItSatisfiesApexMinSdkVersion(t *testing.T) {
+	ctx, _ := testApex(t, `
+		apex {
+			name: "myapex",
+			key: "myapex.key",
+			native_shared_libs: ["mylib"],
+			min_sdk_version: "29",
+		}
+
+		apex_key {
+			name: "myapex.key",
+			public_key: "testkey.avbpubkey",
+			private_key: "testkey.pem",
+		}
+
+		// mylib in myapex will link to mylib2#29
+		// mylib in otherapex will link to mylib2(non-stub) in otherapex as well
+		cc_library {
+			name: "mylib",
+			srcs: ["mylib.cpp"],
+			shared_libs: ["mylib2"],
+			system_shared_libs: [],
+			stl: "none",
+			apex_available: ["myapex", "otherapex"],
+			min_sdk_version: "29",
+		}
+
+		cc_library {
+			name: "mylib2",
+			srcs: ["mylib.cpp"],
+			system_shared_libs: [],
+			stl: "none",
+			apex_available: ["otherapex"],
+			stubs: { versions: ["29", "30"] },
+			min_sdk_version: "30",
+		}
+
+		apex {
+			name: "otherapex",
+			key: "myapex.key",
+			native_shared_libs: ["mylib", "mylib2"],
+			min_sdk_version: "30",
+		}
+	`)
+	expectLink := func(from, from_variant, to, to_variant string) {
+		ld := ctx.ModuleForTests(from, "android_arm64_armv8-a_"+from_variant).Rule("ld")
+		libFlags := ld.Args["libFlags"]
+		ensureContains(t, libFlags, "android_arm64_armv8-a_"+to_variant+"/"+to+".so")
+	}
+	expectLink("mylib", "shared_myapex", "mylib2", "shared_29")
+	expectLink("mylib", "shared_otherapex", "mylib2", "shared_otherapex")
+}
+
 func TestFilesInSubDir(t *testing.T) {
 	ctx, _ := testApex(t, `
 		apex {
@@ -2217,6 +2420,7 @@
 				"otherapex",
 			],
 			recovery_available: true,
+			min_sdk_version: "29",
 		}
 		cc_library {
 			name: "mylib2",
@@ -2228,6 +2432,7 @@
 				"otherapex",
 			],
 			use_apex_name_macro: true,
+			min_sdk_version: "29",
 		}
 	`)
 
@@ -4349,6 +4554,7 @@
 			stl: "libc++",
 			system_shared_libs: [],
 			apex_available: [ "myapex" ],
+			min_sdk_version: "29",
 		}
 	`, withUnbundledBuild)
 
@@ -4749,6 +4955,7 @@
 				"myapex.updatable",
 				"//apex_available:platform",
 			],
+			min_sdk_version: "current",
 		}
 
 		cc_library {
@@ -4761,6 +4968,7 @@
 				"myapex.updatable",
 				"//apex_available:platform",
 			],
+			min_sdk_version: "current",
 		}
 
 		java_library {
@@ -4774,6 +4982,7 @@
 				"myapex.updatable",
 				"//apex_available:platform",
 			],
+			min_sdk_version: "current",
 		}
 
 		java_library {
@@ -4786,6 +4995,7 @@
 				"myapex.updatable",
 				"//apex_available:platform",
 			],
+			min_sdk_version: "current",
 		}
 	`
 
diff --git a/apex/builder.go b/apex/builder.go
index af43417..cef956f 100644
--- a/apex/builder.go
+++ b/apex/builder.go
@@ -234,7 +234,7 @@
 func (a *apexBundle) buildNoticeFiles(ctx android.ModuleContext, apexFileName string) android.NoticeOutputs {
 	var noticeFiles android.Paths
 
-	a.walkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
+	a.WalkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
 		if externalDep {
 			// As soon as the dependency graph crosses the APEX boundary, don't go further.
 			return false
@@ -733,7 +733,7 @@
 	}
 
 	depInfos := android.DepNameToDepInfoMap{}
-	a.walkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
+	a.WalkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
 		if from.Name() == to.Name() {
 			// This can happen for cc.reuseObjTag. We are not interested in tracking this.
 			// As soon as the dependency graph crosses the APEX boundary, don't go further.
diff --git a/cc/cc.go b/cc/cc.go
index ebdb46c..c3b0d88 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -2905,6 +2905,54 @@
 	return true
 }
 
+// b/154667674: refactor this to handle "current" in a consistent way
+func decodeSdkVersionString(ctx android.BaseModuleContext, versionString string) (int, error) {
+	if versionString == "" {
+		return 0, fmt.Errorf("not specified")
+	}
+	if versionString == "current" {
+		if ctx.Config().PlatformSdkCodename() == "REL" {
+			return ctx.Config().PlatformSdkVersionInt(), nil
+		}
+		return android.FutureApiLevel, nil
+	}
+	return android.ApiStrToNum(ctx, versionString)
+}
+
+func (c *Module) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// We ignore libclang_rt.* prebuilt libs since they declare sdk_version: 14(b/121358700)
+	if strings.HasPrefix(ctx.OtherModuleName(c), "libclang_rt") {
+		return nil
+	}
+	// b/154569636: set min_sdk_version correctly for toolchain_libraries
+	if c.ToolchainLibrary() {
+		return nil
+	}
+	// We don't check for prebuilt modules
+	if _, ok := c.linker.(prebuiltLinkerInterface); ok {
+		return nil
+	}
+	minSdkVersion := c.MinSdkVersion()
+	if minSdkVersion == "apex_inherit" {
+		return nil
+	}
+	if minSdkVersion == "" {
+		// JNI libs within APK-in-APEX fall into here
+		// Those are okay to set sdk_version instead
+		// We don't have to check if this is a SDK variant because
+		// non-SDK variant resets sdk_version, which works too.
+		minSdkVersion = c.SdkVersion()
+	}
+	ver, err := decodeSdkVersionString(ctx, minSdkVersion)
+	if err != nil {
+		return err
+	}
+	if ver > sdkVersion {
+		return fmt.Errorf("newer SDK(%v)", ver)
+	}
+	return nil
+}
+
 //
 // Defaults
 //
diff --git a/cc/ndk_prebuilt.go b/cc/ndk_prebuilt.go
index c4d7708..acdc581 100644
--- a/cc/ndk_prebuilt.go
+++ b/cc/ndk_prebuilt.go
@@ -145,6 +145,7 @@
 		libraryDecorator: library,
 	}
 	module.installer = nil
+	module.Properties.Sdk_version = StringPtr("minimum")
 	module.Properties.HideFromMake = true
 	module.Properties.AlwaysSdk = true
 	module.Properties.Sdk_version = StringPtr("current")
diff --git a/cc/testing.go b/cc/testing.go
index 479b424..b5cf45c 100644
--- a/cc/testing.go
+++ b/cc/testing.go
@@ -273,6 +273,7 @@
 			vendor_available: true,
 			recovery_available: true,
 			host_supported: true,
+			min_sdk_version: "29",
 			apex_available: [
 				"//apex_available:platform",
 				"//apex_available:anyapex",
@@ -287,6 +288,7 @@
 			vendor_available: true,
 			recovery_available: true,
 			host_supported: true,
+			min_sdk_version: "29",
 			vndk: {
 				enabled: true,
 				support_system_process: true,
@@ -305,6 +307,7 @@
 			host_supported: false,
 			vendor_available: true,
 			recovery_available: true,
+			min_sdk_version: "29",
 			apex_available: [
 				"//apex_available:platform",
 				"//apex_available:anyapex",
@@ -338,6 +341,7 @@
 			recovery_available: true,
 			vendor_available: true,
 			native_bridge_supported: true,
+			min_sdk_version: "29",
 			stl: "none",
 		}
 
@@ -365,6 +369,7 @@
 			recovery_available: true,
 			vendor_available: true,
 			native_bridge_supported: true,
+			min_sdk_version: "29",
 			stl: "none",
 		}
 
diff --git a/genrule/genrule.go b/genrule/genrule.go
index f6904f1..8b80871 100644
--- a/genrule/genrule.go
+++ b/genrule/genrule.go
@@ -559,6 +559,12 @@
 	}
 }
 
+func (g *Module) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// Because generated outputs are checked by client modules(e.g. cc_library, ...)
+	// we can safely ignore the check here.
+	return nil
+}
+
 func generatorFactory(taskGenerator taskFunc, props ...interface{}) *Module {
 	module := &Module{
 		taskGenerator: taskGenerator,
diff --git a/java/aar.go b/java/aar.go
index 074ead4..500788f 100644
--- a/java/aar.go
+++ b/java/aar.go
@@ -762,6 +762,10 @@
 	return a.depIsInSameApex(ctx, dep)
 }
 
+func (g *AARImport) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	return nil
+}
+
 var _ android.PrebuiltInterface = (*Import)(nil)
 
 // android_library_import imports an `.aar` file into the build graph as if it was built with android_library.
diff --git a/java/app.go b/java/app.go
index c568516..37a6453 100755
--- a/java/app.go
+++ b/java/app.go
@@ -421,8 +421,10 @@
 		if String(a.deviceProperties.Min_sdk_version) == "" {
 			ctx.PropertyErrorf("updatable", "updatable apps must set min_sdk_version.")
 		}
+
 		if minSdkVersion, err := a.minSdkVersion().effectiveVersion(ctx); err == nil {
 			a.checkJniLibsSdkVersion(ctx, minSdkVersion)
+			android.CheckMinSdkVersion(a, ctx, int(minSdkVersion))
 		} else {
 			ctx.PropertyErrorf("min_sdk_version", "%s", err.Error())
 		}
@@ -862,13 +864,13 @@
 	return jniLibs, certificates
 }
 
-func (a *AndroidApp) walkPayloadDeps(ctx android.ModuleContext,
-	do func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool)) {
-
+func (a *AndroidApp) WalkPayloadDeps(ctx android.ModuleContext, do android.PayloadDepsCallback) {
 	ctx.WalkDeps(func(child, parent android.Module) bool {
 		isExternal := !a.DepIsInSameApex(ctx, child)
 		if am, ok := child.(android.ApexModule); ok {
-			do(ctx, parent, am, isExternal)
+			if !do(ctx, parent, am, isExternal) {
+				return false
+			}
 		}
 		return !isExternal
 	})
@@ -880,7 +882,7 @@
 	}
 
 	depsInfo := android.DepNameToDepInfoMap{}
-	a.walkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) {
+	a.WalkPayloadDeps(ctx, func(ctx android.ModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
 		depName := to.Name()
 		if info, exist := depsInfo[depName]; exist {
 			info.From = append(info.From, from.Name())
@@ -900,6 +902,7 @@
 				MinSdkVersion: toMinSdkVersion,
 			}
 		}
+		return true
 	})
 
 	a.ApexBundleDepsInfo.BuildDepsInfoLists(ctx, a.MinSdkVersion(), depsInfo)
@@ -1563,6 +1566,11 @@
 	return sdkSpecFrom("")
 }
 
+func (j *AndroidAppImport) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// Do not check for prebuilts against the min_sdk_version of enclosing APEX
+	return nil
+}
+
 func createVariantGroupType(variants []string, variantGroupName string) reflect.Type {
 	props := reflect.TypeOf((*AndroidAppImportProperties)(nil))
 
diff --git a/java/app_test.go b/java/app_test.go
index e45ba70..120dc00 100644
--- a/java/app_test.go
+++ b/java/app_test.go
@@ -473,6 +473,24 @@
 	}
 }
 
+func TestUpdatableApps_TransitiveDepsShouldSetMinSdkVersion(t *testing.T) {
+	testJavaError(t, `module "bar".*: should support min_sdk_version\(29\)`, cc.GatherRequiredDepsForTest(android.Android)+`
+		android_app {
+			name: "foo",
+			srcs: ["a.java"],
+			updatable: true,
+			sdk_version: "current",
+			min_sdk_version: "29",
+			static_libs: ["bar"],
+		}
+
+		java_library {
+			name: "bar",
+			sdk_version: "current",
+		}
+	`)
+}
+
 func TestUpdatableApps_JniLibsShouldShouldSupportMinSdkVersion(t *testing.T) {
 	testJava(t, cc.GatherRequiredDepsForTest(android.Android)+`
 		android_app {
diff --git a/java/java.go b/java/java.go
index 7a42557..3460ca7 100644
--- a/java/java.go
+++ b/java/java.go
@@ -1887,6 +1887,24 @@
 	return j.depIsInSameApex(ctx, dep)
 }
 
+func (j *Module) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	sdkSpec := j.minSdkVersion()
+	if !sdkSpec.specified() {
+		return fmt.Errorf("min_sdk_version is not specified")
+	}
+	if sdkSpec.kind == sdkCore {
+		return nil
+	}
+	ver, err := sdkSpec.effectiveVersion(ctx)
+	if err != nil {
+		return err
+	}
+	if int(ver) > sdkVersion {
+		return fmt.Errorf("newer SDK(%v)", ver)
+	}
+	return nil
+}
+
 func (j *Module) Stem() string {
 	return proptools.StringDefault(j.deviceProperties.Stem, j.Name())
 }
@@ -2651,6 +2669,11 @@
 	return j.depIsInSameApex(ctx, dep)
 }
 
+func (j *Import) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// Do not check for prebuilts against the min_sdk_version of enclosing APEX
+	return nil
+}
+
 // Add compile time check for interface implementation
 var _ android.IDEInfo = (*Import)(nil)
 var _ android.IDECustomizedModuleName = (*Import)(nil)
@@ -2820,6 +2843,11 @@
 	return j.dexJarFile
 }
 
+func (j *DexImport) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// we don't check prebuilt modules for sdk_version
+	return nil
+}
+
 // dex_import imports a `.jar` file containing classes.dex files.
 //
 // A dex_import module cannot be used as a dependency of a java_* or android_* module, it can only be installed
diff --git a/java/sdk_library.go b/java/sdk_library.go
index 676557e..91869ed 100644
--- a/java/sdk_library.go
+++ b/java/sdk_library.go
@@ -1905,6 +1905,11 @@
 	return false
 }
 
+func (module *SdkLibraryImport) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// we don't check prebuilt modules for sdk_version
+	return nil
+}
+
 func (module *SdkLibraryImport) OutputFiles(tag string) (android.Paths, error) {
 	return module.commonOutputFiles(tag)
 }
@@ -2071,6 +2076,11 @@
 	// do nothing
 }
 
+func (module *sdkLibraryXml) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	// sdkLibraryXml doesn't need to be checked separately because java_sdk_library is checked
+	return nil
+}
+
 // File path to the runtime implementation library
 func (module *sdkLibraryXml) implPath() string {
 	implName := proptools.String(module.properties.Lib_name)
diff --git a/sysprop/sysprop_library.go b/sysprop/sysprop_library.go
index 9f27647..768c8e5 100644
--- a/sysprop/sysprop_library.go
+++ b/sysprop/sysprop_library.go
@@ -310,6 +310,10 @@
 		}}
 }
 
+func (m *syspropLibrary) ShouldSupportSdkVersion(ctx android.BaseModuleContext, sdkVersion int) error {
+	return fmt.Errorf("sysprop_library is not supposed to be part of apex modules")
+}
+
 // sysprop_library creates schematized APIs from sysprop description files (.sysprop).
 // Both Java and C++ modules can link against sysprop_library, and API stability check
 // against latest APIs (see build/soong/scripts/freeze-sysprop-api-files.sh)